hex - UNDERSTANDING how to count trailing zeros for a number using bitwise operators in C

Question

Note - This is NOT a duplicate of this question - Count the consecutive zero bits (trailing) on the right in parallel: an explanation? . The linked question has a different context, it only asks the purpose of signed() being use. DO NOT mark this question as duplicate.

I've been finding a way to acquire the number of trailing zeros in a number. I found a bit twiddling Stanford University Write up HERE here that gives the following explanation.

unsigned int v;      // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;

Why does this end up working ? I have an understanding of how Hex numbers are represented as binary and bitwise operators, but I am unable to figure out the intuition behind this working ? What is the working mechanism ?

Answer 1

The code is broken (undefined behavior is present). Here is a fixed version which is also slightly easier to understand (and probably faster):

uint32_t v;  // 32-bit word input to count zero bits on right
unsigned c;  // c will be the number of zero bits on the right
if (v) {
    v &= -v; // keep rightmost set bit (the one that determines the answer) clear all others
    c = 0;
    if (v & 0xAAAAAAAAu) c |= 1; // binary 10..1010
    if (v & 0xCCCCCCCCu) c |= 2; // binary 1100..11001100
    if (v & 0xF0F0F0F0u) c |= 4;
    if (v & 0xFF00FF00u) c |= 8;
    if (v & 0xFFFF0000u) c |= 16;
}
else c = 32;

Once we know only one bit is set, we determine one bit of the result at a time, by simultaneously testing all bits where the result is odd, then all bits where the result has the 2's-place set, etc.

The original code worked in reverse, starting with all bits of the result set (after the if (c) c--;) and then determining which needed to be zero and clearing them.

Since we are learning one bit of the output at a time, I think it's more clear to build the output using bit operations not arithmetic.