Written on 2025-10-19
This is a list tricks using bit manipulation to perform common logic or arithmetic faster than in a naïve way. Some are trivial, some less so. Some may be implemented by your compiler's optimizer and most will make your code less readable, so use with parsimony. I will try to advertise additions via my RSS feed as I remember/encounter them.
Each trick is accompanied by examples. Those don't serve as proofs of correctness, but should help building intuition for how the tricks work.
Those barely qualify as tricks, but in case you were not aware yet: shifting an integer left/right corresponds to a multiplication/division by 2.
01011 // 11 in base 10 10110 // 22 in base 10 00101 // 5 in base 10
Other well-known tricks include converting an ASCII character to uppercase or lowercase with a boolean & or |, swapping 2 variables, or computing a min/max without branches.
N LSBIt is often useful to build a mask for the n least significant bits of an integer. We can achieve that by computing (1 << n) - 1.
For n = 5:
00100000 // 1 << 5 00011111 // (1 << 5) - 1
Due to how carries work, for a given bit n, the integer right before the one with the nth bit set has all bits lower than n set, which is the mask that we are after.
An integer is by definition a power of 2 if it has exactly 1 bit set, since each bit represents a power of 2. Many CPUs have a POPCNT instruction that returns the number of bits set in an integer, so popcnt(x) <= 0 evaluates to true if x is a power of two. When POPCNT (or an equivalent) is not available, the following trick achieves the same thing:
bool is_power_of_two(size_t x) {
return (x & (x - 1)) == 0;
}
Note that this returns true for n = 0, which is incorrect, but might actually be fine for your use case (it either yields a valid result anyway, or x is never 0 by invariant). If that is not the case, you should also check for the zero.
00010000 // x, a power of 2 00001111 // x - 1 00000000 // x & (x - 1) 00110010 // y, not a power of 2 00110001 // y - 1 00110000 // y & (y - 1)
As explained in the previous trick, if x is a power of 2, then x - 1 has exactly all bits lower than log2(x) set, while x has exactly the log2(x)th bit set. They are mutually exclusive, so a binary & of the 2 is 0. Any other case will be non zero.
a % b is expensive (in the neighborhood of 15-40 clock cycles), but if you know that b is a power of 2, you can compute a & (b - 1) instead, which is much faster.
Note that it is unlikely to be worth checking whether b is a power of 2 and falling back on a regular division, you should rely on invariants instead. Of course, you should profile that on your target, especially if you expect b to often be a power of 2 and that your branch predictor may absorb the overhead enough to beat a regular division.
010110 // a, 22 in base 10 000100 // b, 4 in base 10 000010 // a % b, 2 in base 10 000011 // b - 1 000010 // a & (b - 1)
If b is a power of 2, then b - 1 will be a mask where all bits less significant than b are set. The bits at those positions in a are the remainder of dividing a by b, which is the modulo that we are after, so we just apply that mask with a binary &.
Checking whether an integer is even or odd is a well-known special case of the last trick, where we only mask the last binary digit, and coerce the result to a boolean that indicates whether the value is odd or not.
010111 // x 000001 // x & 1 == 0 -> x is odd 010110 // y 000000 // y & 1 == 0 -> y is even
Same reasoning as the last trick.
https://graphics.stanford.edu/~seander/bithacks.html lists more tricks that you might to also check out.