Check if K-th Bit is Set or Not

by
bit manipulation

In this post about “Check if K-th Bit is Set or NOT“, we are going to discuss about all the methods that you can use to check whether the K-th bit from the right side in the binary representation of a decimal number is set or not.

Here, the set means the value of the bit is 1. The constraint is, k should be less than or equal to the maximum binary bits of the compiler. For Example: For 32-bit compiler: 0<K<33.

Contents show

Check if K-th Bit is Set or Not

Before moving to the solving approach let’s see some example inputs and outputs of the problem statement:

I/P : number = 5, k = 1

=> O/P: Yes

I/P: number = 8, k = 2

=> O/P: No

In the first example, the given number is 5 and the value of k is 1. If we represent 5 in binary form, it will be 101. So, the first bit(k = 1) from the right side is 1 that is set. So, the output is Yes.

In the second case, 8 can be represented in binary as 1000. So, the second bit from the right-hand side is 0(unset) hence the output is No.

Let’s discuss the method to solve this problem programmatically. We are going to discuss two approaches. One is the general method and the other using bit operations.

Check if K-th Bit is Set or Not – General Approach

This approach is simply based on poping out the first (k-1) bits from the right-hand side of the binary representation. Then check the value of K-th bit by taking modulus(%) with 2.

//C++ program to check if K-th bit is set or not - General Approach
#include<bits/stdc++.h>
using namespace std;

int main(){
	int n, k;
	cin>>n>>k;
	
	int i = 1;
	int KthBit;
	while(i){
		if(i == k){
			//Checking the value of Rightmost bit
			KthBit = n%2;
			break;
		}
		//Poping out the rightmost bit
		n = n/2;
		i++;
	}
	
	if(KthBit)
		cout<<"Yes";
	else
		cout<<"No";
		
	return 0;
}

The Time Complexity of this approach is Theta(k). Now, Lets’s see how to check K-th bit of a number in Theta(1) time complexity using bit operators.

Check if K-th Bit is Set or Not – Bit Manipulation Approach

The logic behind this approach is the same as above, just we are going to use Bit operators instead of athematic operators.

But, the main benefit of this approach is in time complexity. With this approach, we are getting Theta(1) time complexity and less code.

//C++ program to check K-th bit is set or not using bit operator
#include<bits/stdc++.h>
using namespace std;

int main(){
	int n, k;
	cin>>n>>k;
	
	//Shifiting 1 by (k-1) times leftward
	if(n&(1<<(k-1)))
		cout<<"Yes";
	else
		cout<<"No";
	
	return 0;
}

As we can see above when we shift 1 by (k-1) time leftward, it gets aligned with the K-th bit of the binary representation of the given decimal number(n).

After that, if we take AND(&) with the resultant number, we will get 1 only if the K-th bit is set else zero.

One slightly different way to write the same thing:

//C++ program to check K-th bit is set or not using bit operator
#include<bits/stdc++.h>
using namespace std;

int main(){
	int n, k;
	cin>>n>>k;
	
	//Here we are left shifiting 1 to (k-1) times
	if((n>>(k-1))&1)
		cout<<"Yes";
	else
		cout<<"No";
	
	return 0;
}

Here we are right shifting the K-th bit of given number(n) towards rightward by (k-1) time. After shifting, the K-th bit of the given decimal number comes to the front. And as we take it’s AND(&) with 1, It will return either 1 or 0. If it returns 1, means K-th bit is also 1(set) hence “Yes” gets printed otherwise “No”.

Also Check: Addition without plus operator using Bits

Leave a Comment