Bit tricks look like magic until you write the numbers out in binary. Each one below includes the expression, a short explanation, and an 8-bit example you can reproduce in the Binary Bitwise Calculator. They appear in coding interviews, but they also show up in real code: allocators, hash tables, graphics, compression, and kernels.
The examples assume unsigned integers unless stated otherwise.
1. Check if a Number Is Even or Odd
bool odd = n & 1;Bit 0 is the only bit with an odd place value. 46 = 00101110 ends in 0, so it is even.
2. Check if a Number Is a Power of Two
bool pow2 = n != 0 && (n & (n - 1)) == 0;A power of two has exactly one 1 bit. Subtracting 1 turns that bit into 0 and every bit below it into 1, so the AND is zero:
n = 00100000 (32)
n - 1 = 00011111 (31)
AND = 00000000For any other number, a higher 1 bit survives the AND.
3. Clear the Lowest Set Bit
n &= n - 1;The same n − 1 effect, applied to any number. 46 = 00101110 becomes 00101100 (44). Repeating this until n is zero counts the 1 bits, a method known as Kernighan’s algorithm:
int popcount(unsigned n) {
int count = 0;
while (n) { n &= n - 1; count++; }
return count;
}It loops once per set bit rather than once per bit.
4. Isolate the Lowest Set Bit
unsigned low = n & -n; /* or n & (~n + 1) */In two’s complement, −n is ~n + 1. All bits above the lowest 1 are inverted, so only that one bit survives the AND. 46 & −46 = 2. Fenwick trees (binary indexed trees) use this to jump between nodes.
5. Set, Clear, Toggle, and Test Bit k
n |= (1u << k); /* set */
n &= ~(1u << k); /* clear */
n ^= (1u << k); /* toggle */
bool on = (n >> k) & 1; /* test */These are the four mask operations covered in the Bit Masking Guide.
6. Swap Two Variables With XOR
a ^= b; b ^= a; a ^= b;It works because XOR is its own inverse. It is a nice puzzle, but in practice a temporary variable is clearer and at least as fast. It also zeroes the value if a and b are the same variable.
7. Check if Two Integers Have Opposite Signs
bool opposite = (a ^ b) < 0; /* signed ints */XOR sets the sign bit of the result only when the two sign bits differ.
8. Absolute Value Without Branching
int mask = x >> 31; /* 0 for x >= 0, -1 for x < 0 (32-bit int) */
int absx = (x + mask) ^ mask;For negative x, adding −1 and then XORing with all ones is the same as ~(x − 1), which equals −x. This relies on arithmetic right shift of negative values, which is implementation-defined in C (though universal in practice). Modern compilers generate branchless code from abs() anyway, so treat this as a learning exercise.
9. Round Up to the Next Power of Two
uint32_t next_pow2(uint32_t v) {
v--;
v |= v >> 1; v |= v >> 2; v |= v >> 4;
v |= v >> 8; v |= v >> 16;
return v + 1;
}The OR cascade copies the highest 1 bit into every position below it, producing a run like 00111111. Adding 1 gives the next power of two. next_pow2(46) returns 64. Hash tables and memory allocators use this to size buckets.
10. Modulo by a Power of Two
unsigned r = n & (size - 1); /* same as n % size when size is a power of two */46 & 7 = 6, and 46 % 8 = 6. Ring buffers rely on this to wrap their indexes without division.
11. Enumerate All Subsets of a Set
Represent each subset of n items as an n-bit mask. Counting from 0 to 2^n − 1 visits every subset:
items = ["a", "b", "c"]
for mask in range(1 << len(items)):
subset = [items[i] for i in range(len(items)) if mask >> i & 1]
print(f"{mask:03b}", subset)This prints 8 lines, from 000 [] to 111 ['a', 'b', 'c']. Dynamic-programming solutions over subsets (“bitmask DP”) use exactly this representation.
12. Get the Index of the Highest or Lowest Set Bit
Most compilers and languages expose hardware instructions for these:
| Task | C / C++ (GCC, Clang) | C++20 | Python |
|---|---|---|---|
| count 1 bits | __builtin_popcount(x) | std::popcount(x) | x.bit_count() |
| trailing zeros | __builtin_ctz(x) | std::countr_zero(x) | (x & -x).bit_length() - 1 |
| leading zeros | __builtin_clz(x) | std::countl_zero(x) | 32 - x.bit_length() |
Use these instead of loops when performance matters. Note that the GCC builtins are undefined for x == 0.
When to Use Bit Tricks
Bit tricks are worth using when they make code shorter and clearer to someone who knows the idiom, such as n & (n − 1) for power-of-two checks, or when profiling shows a real hot spot. They are not worth it when they hide intent. Compilers already turn n % 8 into n & 7 and n * 4 into n << 2 for unsigned values.
A good habit: when you use a trick, add a one-line comment naming it, and test it at the edges (zero, one, the maximum value, and negative numbers for signed types). The Bitwise Calculator is a quick way to check those edge cases at a fixed width.
