Fastest way to read Left-Most bit from unsigned int (C++) ?

Question

Hello,
What is the fastest way to read the Left-Most bit from unsigned int ?

Thanks,
SW

Answer 1

On a 32-bit system using any compiler that a normal human would use, without odd, esoteric edge cases that C++ geeks can't seem to avoid getting excited about, planet Earth, circa 2010, stars unaligned, a normal day:

if (value & 0x8000000) { ... }

Answer 2

i >> (sizeof(unsigned int) * CHAR_BIT - 1)

The sizeof, multiplication, and subtraction will be computed at compile-time by any reasonable compiler, so this should become a single right-shift instruction, which is about as fast as you will get.

Answer 3

Well that depends on the size of int, endianness, and whether you want the left most bit based on orientation within memory or the most significant bit.

Guessing that you want the most significant bit, which on a little endian, 32 bit machine (the most common kind), would be in the fourth byte from the ints location in memory.:

i & 0x80000000

Now the register is a boolean for the presence of the MSB bit.

It might be possible to bit shift to the right, this may generate less object code:

i >> (sizeof(i) * CHAR_BIT - 1)

Update0

Maybe some aren't aware of what I mean above. On the example architecture I gave you could also do this:

((unsigned char *)&i)[3] >> 7
((unsigned char *)&i)[3] & 0x80

Answer 4

Might be faster than shifting at run-time, if AND is faster than shifting:

i & (1 << (sizeof(unsigned int) * CHAR_BIT - 1))

Answer 5

#define MSB ~(~0U >> 1 )

breaking it down assuming 8 bits int for example purposes.

0U = 00000000b
~0U = 11111111b
~0U >> 1 = 01111111b
~(~0U >> 1) = 10000000b

then AND this value with what you want to test ( cast as unsigned int )

(unsigned int ) a & MSB;

Answer 6

You could of course also try this:

((int) myUint) < 0 // true if set, otherwise false

And use the fact, that for signed integers, the left most bit is set for negative numbers.

This should also be pretty fast, since the cast is a compile-time thing, and does not really have to be executed - it just tells the compiler to use the signed opcodes as opposed to the unsigned ones. So I believe a single instruction (CMP?) needs to be executed...

Answer 7

How about this?

i >> numeric_limits<unsigned>::digits - 1;