Math hacks and other tricks¶
Being able to exploit the bit representation of memory enables some clever hacks and performance tweaks. Useful for microoptimization, I also appreciate these sort of tricks purely for their wit.
Masking remainders¶
Knowing only that numbers are stored in base two, masking low-order bits
enables a cheap version of modulo aka remainder. For example, the usual
way to test whether a number \(x\) is even is x % 2 == 0.
Taken literally, the % operator implies division; however, in
base two, a number is even precisely when it has a 0 in its one’s place,
so an equivalent test is x & 1 == 0 or even just ~x & 1.
The corresponding negations can represent oddness.
It doesn’t stop at the one’s place; x & 0x3 masks \(x\)
to keep only the bottom two bits, which is the same as x % 4.
In general, x & ((1 << n) - 1) is the same as the remainder
of \(x÷2^n\).
Compilers are good at this sort of optimization, so ordinarily you can
just write x % 2 and count on the compiler to generate a masking
operation rather than a division. Try it!
Exploiting twos’ complement notation¶
At the other end of a number, the most significant bit of a twos’
complement number can reveal whether the number is negative. Given a
32-bit signed integer x, for example, x >> 31 is true
precisely when x < 0.
When you negate a two’s complement number with e.g. -x, that
is equivalent to ~x + 1, but you’d have to be in a very unusual
situation indeed before that made sense to do manually.
Originally, C did not require twos’ complement to be the internal representation of integral types, so this trick was not portable. In practice, nearly all implementations did use twos’ complement, and in the 2020 version of the C standard twos’ complement was at last formally required.
For those old and unorthodox systems that use(d) one’s complement or sign–magnitude notations for their signed numbers, testing whether a number is negative or negating the sign of the number are also possible with bit hacks, just different ones.
Population count…¶
As just one example of the deeper realm of what is possible in bit hacks,
consider counting how many bits are set in an unsigned 32-bit integer
x, from 0 (when x == 0) to 32 (when x is the
largest possible 32-bit integer, with all its bits set to 1). This is
called Hamming weight, (binary) digit sum, or population count. For
example, the population count of 5 is 2 (\(101_2\) has 2 bits set).
The naïve way would be to loop over all of the bits and count how many are set, with the tools we’ve already explored.
unsigned int count = 0;
while (x) { // while any bits remaining are set
count += x & 1; // count if least significant bit is set
x >>= 1; // shift all bits down
}
We can do better with a clever trick that clears the least significant 1
in x, without iteration to find it.
unsigned int count = 0;
while (x) {
count++;
x &= x - 1;
}
There is a detailed discussion on the Wikipedia page for Hamming weight regarding even more optimized population count algorithms that are well worth exploring in detail.
Of course, if you know what architecture you are on, you can often
use a machine instruction for this very common operation. On x86-64,
for example, there is a popcnt instruction.
…and beyond!¶
Sean Eron Anderson has compiled a staggeringly detailed and rigorous collection of Bit Twiddling Hacks, from which I have drawn heavily for writing this page and which I encourage you to read for yourself. Learn about hacks I haven’t even mentioned, and perhaps see if you can follow along through how they work or try using them in code you write for class to practice bit twiddling.