how to find left most 1 in a 32bit int in C [duplicate]

Question

Possible Duplicate:
Find the highest order bit in C

How can I write a C function that will generate a mask indicating the leftmost 1 in x.

Ex: 0xFF00 -> 0x8000, and 0x6600 -> 0x4000. So far:

int left1(unsigned x){}

I understand, 0xFF00 == 1111 1111 0000 0000.. and 0x6600 == 0110 0110 0000 0000.. but I'm stumped after that.

Answer 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;

Answer 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;