How to get position of right most set bit in C

Question

int a = 12;

for eg: binary of 12 is 1100 so answer should be 3 as 3rd bit from right is set.

I want the position of the last most set bit of a. Can anyone tell me how can I do so.

NOTE : I want position only, here I don't want to set or reset the bit. So it is not duplicate of any question on stackoverflow.

Solution 1

Try this

int set_bit = n ^ (n&(n-1));

Explanation:
As noted in this answer, n&(n-1) unsets the last set bit.
So, if we unset the last set bit and xor it with the number; by the nature of the xor operation, the last set bit will become 1 and the rest of the bits will return 0

Solution 2

This answer Unset the rightmost set bit tells both how to get and unset rightmost set bit for an unsigned integer or signed integer represented as two's complement.

get rightmost set bit,

x & -x
// or
x & (~x + 1)

unset rightmost set bit,

x &= x - 1
// or
x -= x & -x  // rhs is rightmost set bit

why it works

x:                     leading bits  1  all 0
~x:           reversed leading bits  0  all 1
~x + 1 or -x: reversed leading bits  1  all 0
x & -x:                       all 0  1  all 0

eg, let x = 112, and choose 8-bit for simplicity, though the idea is same for all size of integer.

// example for get rightmost set bit
x:             01110000
~x:            10001111
-x or ~x + 1:  10010000
x & -x:        00010000

// example for unset rightmost set bit
x:             01110000
x-1:           01101111
x & (x-1):     01100000

Solution 3

Finding the (0-based) index of the least significant set bit is equivalent to counting how many trailing zeros a given integer has. Depending on your compiler there are builtin functions for this, for example gcc and clang support __builtin_ctz. For MSVC you would need to implement your own version, this answer to a different question shows a solution making use of MSVC intrinsics.

Given that you are looking for the 1-based index, you simply need to add 1 to ctz's result in order to achieve what you want.

int a = 12;
int least_bit = __builtin_ctz(a) + 1; // least_bit = 3

Note that this operation is undefined if a == 0. Furthermore there exist __builtin_ctzl and __builtin_ctzll which you should use if you are working with long and long long instead of int.

Solution 4

The leftmost bit of n can be obtained using the formulae: n & ~(n-1)

This works because when you calculate (n-1) .. you are actually making all the zeros till the rightmost bit to 1, and the rightmost bit to 0. Then you take a NOT of it .. which leaves you with the following: x= ~(bits from the original number) + (rightmost 1 bit) + trailing zeros

Now, if you do (n & x), you get what you need, as the only bit that is 1 in both n and x is the rightmost bit.

Phewwwww .. :sweat_smile:

http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/ helped me understand this.

Solution 5

One can use the property of 2s-complement here.
Fastest way to find 2s-complement of a number is to get the rightmost set bit and flip everything to the left of it.
eg: consider a 4 bit system
4=0100
2s complement of 4 = 1100, which nothing but -4
4&(-4)=0100.
Notice that there is only one set bit and its at rightmost set bit of 4
Similarly we can generalise this for n.
n&(-n) will contain only one set bit which is actually at the rightmost set bit position of n.
since there is only one set bit in n&(-n) , it is a power of 2.
So finally we can get the bit position by:

log2(n&(-n))+1

View more solutions