Help Me Figure Out This Trick

Occasionally the Wizards of C concoct a mad method to perform some magical feat on a number. This sorcery cannot be explained using those scant, basic math concepts known to me. So perhaps you’d like to invest a few moments to review what I consider to be one of the most insane ways to discover the maximum power of two that can divide any integer.

I’m sure this black magic has something to do with the binary representation of integer values. I’ll probe this theory in a a few paragraphs. But first, here is the code, which I stole from the Internet:

2022_08_27-Lesson.c

#include <stdio.h>

int main()
{
    int v;

    for( v=0; v<1050; v++ )
        printf("-%d & %d = %d\n",
                v,
                v,
                -v & v
              );

    return(0);
}

The for loop generates values from 0 through 1049, mostly to show how the conjuring affects different numbers. Here’s a chunk of the sample run:

-184 & 184 = 8
-185 & 185 = 1
-186 & 186 = 2
-187 & 187 = 1
-188 & 188 = 4
-189 & 189 = 1
-190 & 190 = 2
-191 & 191 = 1
-192 & 192 = 64

The true mystery happens within the printf() statement: -v & v This expression must be unraveled to discover the dark art behind the witchcraft. Or, without the flowery writing, what happens at the binary level to generate such accurate output?

I’ll work with the value 188, shown in the output, which has a highest power-of-two value of four. Running 188 through the code found in the Factors Lesson in 2018, I see the following output:

Enter a positive integer: 188
Factors of 188:
1
2
4
47
94
188

The highest power of two in this output is four, which agrees with the output from this week’s Lesson. The next step is to look at the binary values of -188 and 188:

Decimal Hex Binary
188 0xBC 0000 0000 1011 1100
-188 0xBC 1111 1111 0100 0100

The binary representation of a negative integer sets a lot of bits. This approach explains how the range for a 32-bit signed int value (Binary column above) goes from -32,768 to 32,767. Once the bits flip from 32,767 to the next integer, the sign bit is flipped. This flipping makes the value negative, hence the next value after 32,767 is -32,768. Shocking, I know.

The bitwise AND operator (&) compares each bit in the negative and positive versions of the same value. The difference isn’t just one bit; no it’s a buncha bits as witnessed in the above table. Based on the bitwise operation, only when both bits in the two values match is the result true. Figure 1 illustrates how this operation works on the values 188 and -188.

Figure 1. How the binary math works for v & -v.

From the Figure, you see that only one bit matches between the two values. Its value is the greatest common power-of-two factor for the value 188, four. This illustration explains the how, but it still doesn’t answer why.

I’m certain some math genius out there knows what’s going on. Is it coincidence? I can only guess that it’s just some effect of binary numbers and their positive/negative representation. Still the expression -v & v is kinda cool and definitely works. It remains an interesting mystery.

Leave a Reply