How does this code for getting the lowest bit position work?

Question

unsigned GetLowestBitPos(unsigned value)
{
   double d = value ^ (value - !!value); 
   return (((int*)&d)[1]>>20)-1023; // This is what I really need help understanding. 
}

It looks to me that the code is casting a double into a pointer to an integer. I'm not sure what the [1] is used for. Then it looks like we are bit shifting by 20 bits to the right

I would appreciate any help on this code. Its been a while since I have programmed with C++ and I'm trying to write logic for a Programmable Logic Controller (PLC) to do the same thing if it is possible.

Thanks for any help

Replace the double with unsigned long long, it should reduce the confusion. There is not magical double precision IEEE754 related computation going on, double is used here because its 8 bytes (64-bit) of data and nothing else. — , Jan 22 '11 at 06:31
@Zenikoder, no, this is extracting the double's exponent to find the top bit position. using an unsigned long long would... not do anything very interesting, really. Try it for yourself and see :) — bdonlan, Jan 22 '11 at 06:35
The first operation is described at the very begining of the Basic section of Hacker's Delight: http://www.hackersdelight.org/ — ruslik, Jan 22 '11 at 14:57

score 6 · Answer 1 · edited May 23 '17 at 12:18

Let's take this one step at a time. First:

double d = value ^ (value - !!value);

If value = 0, then this evaluates to 0 ^ (0 - 0), so d is 0. If value != 0, then this evaluates to value ^ (value - 1). This has the effect of setting the lowest one bit, and lowest zero bits of value to one, and all other bits to zero. eg:

value = 010100100
d     = 000000111

This occurs because (value - 1) is the same as value, except that the lowest string of zero bits become one, and the next one bit becomes zero, due to carrying

value     = 010100100
value - 1 = 010100011
XOR value = 000000111

In any case, d is loaded with the floating point value of this. The next line:

return (((int*)&d)[1]>>20)-1023;

This extracts the floating point exponent, and adds back the bias. Note that this assumes a little endian system, such as x86; on a big endian system you'd need to use [0]. It also makes assumptions about the size of ints and doubles - in particular, it assumes 32-bit ints, and 64-bit IEEE floats for doubles.

The key here is that non-denormalized IEEE floating point values (and a 32-bit int in a double will always be non-denormalized) end up with a representation looking a bit like 1.xxxxxxxx * 2^(e-1023), where xxxxxxxx is the fractional component, and e is the exponent. Since you've arranged the ones bit of interest to be the highest order ones bit, the exponentends up with the value you're looking for.

That said, you probably won't be able to use this on a PLC - although it's a pretty clever hack, it's only even remotely efficient if you have a hardware FPU; and even on x86 systems there are faster built-in integer operations. There are a number of other techniques in this SO question; you'll probably be able to find a faster one there. Your PLC also may have a built-in operation to do this in one instruction as well.

How does this code for getting the lowest bit position work?

1 Answers1