Sometimes the Wizards of C concoct a mad technique to carry out some magical feat on a quantity. This sorcery can’t be defined utilizing these scant, fundamental math ideas identified to me. So maybe you’d like to take a position a number of moments to assessment what I think about to be probably the most insane methods to find the utmost energy of two that may divide any integer.
I’m certain this black magic has one thing to do with the binary illustration of integer values. I’ll probe this principle in a a number of paragraphs. However first, right here is the code, which I stole from the Web:
2022_08_27-Lesson.c
#embrace <stdio.h>
int most important()
{
int v;
for( v=0; v<1050; v++ )
printf("-%d & %d = %dn",
v,
v,
-v & v
);
return(0);
}
The for loop generates values from 0 by 1049, principally to point out how the conjuring impacts completely different numbers. Right here’s a bit of the pattern 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 thriller occurs throughout the printf() assertion: -v & v This expression should be unraveled to find the darkish artwork behind the witchcraft. Or, with out the flowery writing, what occurs on the binary degree to generate such correct output?
I’ll work with the worth 188, proven within the output, which has a highest power-of-two worth of 4. Operating 188 by the code discovered within the Components Lesson in 2018, I see the next output:
Enter a optimistic integer: 188
Components of 188:
1
2
4
47
94
188
The very best energy of two on this output is 4, which agrees with the output from this week’s Lesson. The subsequent step is to take a 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 illustration of a destructive integer units a variety of bits. This method explains how the vary for a 32-bit signed int worth (Binary column above) goes from -32,768 to 32,767. As soon as the bits flip from 32,767 to the following integer, the signal bit is flipped. This flipping makes the worth destructive, therefore the following worth after 32,767 is -32,768. Surprising, I do know.
The bitwise AND operator (&) compares every bit within the destructive and optimistic variations of the identical worth. The distinction isn’t only one bit; no it’s a buncha bits as witnessed within the above desk. Based mostly on the bitwise operation, solely when each bits within the two values match is the end result true. Determine 1 illustrates how this operation works on the values 188 and -188.
Determine 1. How the binary math works for v & -v.
From the Determine, you see that just one bit matches between the 2 values. Its worth is the best frequent power-of-two issue for the worth 188, 4. This illustration explains the how, but it surely nonetheless doesn’t reply why.
I’m sure some math genius on the market is aware of what’s happening. Is it coincidence? I can solely guess that it’s just a few impact of binary numbers and their optimistic/destructive illustration. Nonetheless the expression -v & v is kinda cool and undoubtedly works. It stays an attention-grabbing thriller.
