how to find left most 1 in a 32bit int in C
18,820
Solution 1
You can do this in two parts: first, use a technique called "bit smearing" to ensure that all the bits to the right of the first 1 are also 1:
x |= x >> 16;
x |= x >> 8;
x |= x >> 4;
x |= x >> 2;
x |= x >> 1;
At this point, an input of 0xFF00
will leave x
equal to 0xFFFF
, and an input of 0x6600
will leave x
equal to 0x7FFF
. We can then leave just the highest 1
set using:
x ^= x >> 1;
Solution 2
Count the number of times it takes to bit-shift to the right until you reach 1, then bit-shift that 1 to the left by that same count.
int ct=0;
while (x > 1) { ct++; x = x >> 1; }
x = x << ct;
Author by
sebi
Updated on June 04, 2022Comments
-
sebi almost 2 years
Possible Duplicate:
Find the highest order bit in CHow can I write a C function that will generate a mask indicating the leftmost
1
inx
.Ex:
0xFF00 -> 0x8000
, and0x6600 -> 0x4000
. So far:int left1(unsigned x){}
I understand,
0xFF00 == 1111 1111 0000 0000..
and0x6600 == 0110 0110 0000 0000..
but I'm stumped after that. -
alveko almost 11 yearsShouldn't the first part be in the opposite order?
-
caf almost 11 years@alveko: It works just as well either way.
-
Don Scott about 10 yearsThis does NOT work with negative numbers because the sign bit is sticky.
-
caf about 10 years@don4of4: The question specifies
unsigned
as the type of the input number.