5

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.

4
  • 1
    use bit shifting >> and masking &
    – TJD
    Sep 14, 2012 at 0:09
  • If you cast it as signed, could you not do (x<0)?
    – ratbum
    Sep 14, 2012 at 0:10
  • How do you deal with endianess in this scenario? The left-most bit may not be the high bit Sep 14, 2012 at 0: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, 2012 at 0:31

3 Answers 3

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;
4
  • Shouldn't the first part be in the opposite order?
    – alveko
    May 28, 2013 at 15:23
  • @alveko: It works just as well either way.
    – caf
    May 28, 2013 at 21:18
  • This does NOT work with negative numbers because the sign bit is sticky.
    – Don Scott
    Jan 25, 2014 at 2:03
  • 4
    @don4of4: The question specifies unsigned as the type of the input number.
    – caf
    Jan 28, 2014 at 3:08
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;
0
0

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!

Not the answer you're looking for? Browse other questions tagged or ask your own question.