Check if K-th Bit is Set or Not

In this post about ““, we are going to discuss about the methods you can use to check whether the 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:.

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 , 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.

The Time Complexity of this approach is Theta(k). Now, Lets's see 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.

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 the same thing:

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