Understanding a function that uses binary operands to count the number of 1s in a binary number

Question

Recently I've run across this question that asks you to return the number of consecutive ones in a binary string, going from left to right (so 11101001 = 3, 011111 = 0, 111101 = 4, etc). The catch is to do it using only binary operands, and without any sort of loops.

After looking around online for a bit (thanks Google), I found this solution someone else came up with, and would like better help understanding it.

int leftBitCount(int x) {
    int v = x;
    int r;  // store our result here
    int shift;
    int full = !(~x); // we must add one if we have 0xffffffff

    // Check the top 16 bits and add them to our result if they exist
    r     = !(~(v>>16)) << 4;
    v   <<= r;
    // check the remaining 8 bits
    shift = !(~(v >> 24)) << 3;
    v   <<= shift;
    r    |= shift;
    // remaining 4 bits
    shift = !(~(v>>28)) << 2;
    v   <<= shift;
    r    |= shift;
    // remaining 2 bits
    shift = !(~(v >> 30)) << 1;
    v   <<= shift;
    r    |= shift;
    // remaining 1 bits
    r    ^= 1&((v>>31));

    // remember to add one if we have 32 on bits
    return r + full;
}

From what I can tell, the function apparently checks the first 16 bits of the 32 bit integer, then goes to next 8 depending on whether they were all 1s, then the next 4 depending whether those were all 1s, then 2, then 1, etc.

Unfortunately, I'm kind of lost as to how exactly the code accomplishes this, and would like some help understanding.

For example, here:

r     = !(~(v>>16)) << 4;
v   <<= r;

I can see that v is being shifted and negated, but am at a loss as to how this helps solve anything.

Answer 1

Okay,

    int full = !(~x); // we must add one if we have 0xffffffff

The bitwise negation operator (~) flips all the pits in its operand. If all bits in the operand are set then the result is zero, which the logical negation operator (!) converts to the value 1 (true). Otherwise, the logical negation converts its operand to 0 (false).

    // Check the top 16 bits and add them to our result if they exist
    r     = !(~(v>>16)) << 4;

Operand v, assumed to be 32 bits wide, is right-shifted so that the top half of its bits are end up in the bottom 16 bits of the result. It appears that the code assumes (unsafely) that the vacated bits will be one-filled if the sign bit is set (i.e. an arithmetic shift), so that if the top 16 bits of the original number are all set then the bitwise negation produces zero, which the logical negation converts to 1. Left shifting 1 (== 2^0) by four places yields 16 (== 2^4), which is the number of bits in question. If not all of the top 16 bits are 1 (or some but not all of those bits are set, and the right shift shifts in zeroes instead of ones) then you end up with 0 << 4, which is, of course, 0.

    v   <<= r;

The number of bits we just computed (either 16 or zero) are shifted off to the left. We now consider either a smaller chunk of the original top bits, or a smaller-size piece of the other bits, now shifted into the top position.

    shift = !(~(v >> 24)) << 3;
    v   <<= shift;

Same game as before, but now we're considering only an 8-bit chunk.

    r    |= shift;

Adds the number of bits just measured (8 or zero) to the result.

The rest continues in the same pattern, to here:

    r    ^= 1&((v>>31));

which simply flips the bottom bit of the result if the top bit of v is set; since to this point the code has left that bit unset, the ^= could as easily be += or |=. Then we have:

    return r + full;

Remember that full took the value 1 if the argument had all bits set, otherwise zero. The foregoing code has exhausted all the tricks it can play to set one bit of r at a time, as it just finished with the least-significant bit. If there is indeed one more bit set in the input value, then you need either to add 1 to the result with the + operator or to simulate a 6-bit adder.

Note well: this code appears to rely on some implementation defined behavior to do its job. You would avoid implementation-definedness by using unsigned integers instead of signed ones. You would still need to fix the expressions a bit, but I leave that to you to work out.

Answer 2

r = !(~(v>>16)) << 4;

Here's what's happening on this line:

1. v >> 16 shifts the value of v (which at this time is the value of x) 16 places to the right. The bottom 16 bits of this expression are the top 16 bits of v, and the top 16 bits of this expression, interestingly, are implementation-defined. The C compilers I've worked with have performed a right shift of a signed value as an arithmetic shift, and the code you posted seems to be counting on this fact, but it's not necessarily the case. See the answers to this question for details.

2. The ~ operator performs a bitwise complement of the value produced in step 1. The important observation here is that if and only if (a) the top 16 bits of v were all 1s, and (b) the C compiler being used performs an arithmetic shift, then all the bits of the expression in step 1 will be 1s, which means that ~(v>>16) will be zero.

3. The ! operator performs a logical negation of the value produced in step 2, which means that !(~(v>>16)) will be 1 if and only if the value in step 2 is zero (meaning that the top 16 bits of v are all 1s). Otherwise, this value will be zero.

4. Finally, the << 4 is just a multiplication by 16. So r is assigned the value 16 if the top 16 bits of x were set to 1, or the value zero if any of the top 16 bits were 0s (or if the C compiler being used performs a logical right shift).

Next, this line:

v <<= r;

If the top 16 bits of v are all 1s—meaning that the value of r is 16—then we don't need to examine those bits any further, so this line shifts v to the left by 16 bits, which essentially discards those top 16 bits that we've already examined, and places the eight next-most-significant bits in the topmost positions, so we can examine those next.

If, on the other hand, the top 16 bits of v are not all 1s—meaning that the value of r is 0—then the bottom 16 bits of v become irrelevant, because whatever the number of leading 1 bits in v is, we know that it must be less than 16. So in that case, v <<= r leaves the value of v untouched, and we proceed to the next step by examining the eight original topmost bits in v.

The rest of the algorithm basically repeats these steps, except that the number of bits being examined falls by half in each step. So this bit of code checks the top 8 bits:

shift = !(~(v >> 24)) << 3;
v <<= shift;
r |= shift;

The only thing different here is that r is being augmented with a logical OR rather than being assigned directly as it was in the 16-bit step. This is functionally equivalent to addition in this case, because we know that the value of r was previously 0 or 16, and the value of shift is likewise either 0 or 8, and none of those values' 1 bits occur in corresponding positions. Then this bit of code does the same with the top 4 bits:

shift = !(~(v>>28)) << 2;
v <<= shift;
r |= shift;

Then the top 2:

shift = !(~(v >> 30)) << 1;
v <<= shift;
r |= shift;

And finally, the top 1:

r ^= 1&((v>>31));

The number of bits thus tested is 16 + 8 + 4 + 2 + 1 = 31, which is obviously one shy of the total number of bits in the original value, and thus not sufficient in the case where all 32 bits are 1s. Assuming that all 32 bits are 1s, here's how the original value of x will be shifted in each step:

16-bit step: 123456789ABCDEFGHIJKLMNOPQRSTUVW
 8-bit step: HIJKLMNOPQRSTUVW----------------
 4-bit step: PQRSTUVW------------------------
 2-bit step: TUVW----------------------------
 1-bit step: VW------------------------------

The one that's never considered by the code seen thus far is the W bit, the least significant bit of the original value. That bit will be part of the result if and only if all bits to the left of it are 1s, meaning that all bits in the value are 1s, and this is the purpose of the check performed at the top of the code:

 int full = !(~x);

This is the same combination of bitwise complement and logical negation we saw earlier; ~x will be zero if and only if all of the bits in x are 1s, and so !(~x) will be 1 in that case and zero in any other case.