CODEWITHSUNDEEP
c++bit
sagar saini
sagar saini

Reputation: 107

How to find the leftmost bit of an number in one line

How to find out the leftmost bit and rightmost bit of an number in one line of code ?

Well we can traverse an loop to find out the leftmost set bit by leftshift but how to do it in one line to make an another no. whose leftmost bit / rightmost bit is set ? Like y = x & ~(x-1) will find leftmost bit but I didn't get this how ?

Can someone give the code for that in C++ and explain ?

Upvotes: 1

Views: 3584

Answers (1)

Alain Merigot
Alain Merigot

Reputation: 11537

For the rightmost bit, there is a well-known trick.

x=x & -x

will clear all set bits in x, except the rightmost one. You will find many explanations why this works in SO (see for instance this answer)

To find its index, except by using builtins of programming languages, there is no way but doing a loop AFAIK. Note that this loop can be unrolled to have a one liner.

pos = (16*(x&0xffff0000)!=0) + (8*(x&0xff00ff00)!=0) + (4&(x&0xf0f0f0f0)!=0) + (2*(x&0x66666666)!=0)+(x&0xaaaaaaaa)!=0)

x is the result of the previous operation (ie only the rightmost bit is set) and it works by testing is this bit is in the upper half word in which case the position will be > 16, then an even byte, even nibble, and so on.

Another solution, is to use the mathematic operator log2

pos=(int)log2((double)x)

For the left most bit, AFAIK, there are no way to do that at the bit level, except through loops. But it is possible to use log2() to find the position of the leftmost bit.

Then, to return an int with only this bit set, one can use right shifts.

x = 1 << ((int) log2((double)x))

This will keep only the left most bit in x.

Beware to previously check if x in non null.

Upvotes: 5

Related Questions