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

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.

How do you deal with endianess in this scenario? The left-most bit may not be the high bit — Richard J. Ross III, Sep 14 '12 at 00:16
@RichardJ.RossIII: Without any further elaboration, the implication is that "leftmost" means "most significant", since that's how we write numbers. — caf, Sep 14 '12 at 00:31

score 16 · Answer 1 · answered Sep 14 '12 at 00:26

16

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;

answered Sep 14 '12 at 00:26

caf

233,326
40
323
462

Shouldn't the first part be in the opposite order? – alveko May 28 '13 at 15:23
@alveko: It works just as well either way. – caf May 28 '13 at 21:18
This does NOT work with negative numbers because the sign bit is sticky. – Don Scott Jan 25 '14 at 02:03
4

@don4of4: The question specifies `unsigned` as the type of the input number. – caf Jan 28 '14 at 03:08

phatfingers · Answer 2 · 2012-09-14T00:33:20.040

3

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;

edited Sep 14 '12 at 00:33

answered Sep 14 '12 at 00:13

phatfingers

9,770
3
30
44

score 0 · Answer 3 · answered Sep 14 '12 at 00:18

One approach is to create a bitmask, and then right-shift the value.

That is, create a bitmask so that your integer is '1000....' or '0.....' - depending on whether that first bit is a 0 or a 1.

Then take that integer and right-shift it until it becomes the least-significant-bit, rather than the most-significant. As an example, 0b10000000 >> 8 is 1.

So first, depending on the size of your integer, you have to shift, well, however many bits are relevant.

Then you have to create the bitmask. Let's just take a 1-byte integer:

unsigned int i = 1 << 8 would create an integer i whose most significant bit is a 1.

Or you could use hex. You already know that 0xFF == 11111111. You can actually break it up further: 0xF0 == 11110000

Since 0xF == 1111 in binary, well, we will do the reverse. 1000 in binary is what, in hex? 1000 in binary is the number 8, which also happens to equal 0x8

So, for a single byte, the mask for the leftmost bit is 0x80.

Now! Apply this to 32 bits!

Good luck!

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

3 Answers3