Bit Manipulation Cheat Sheet

Common tricks and patterns every developer should know

Bit Operations Quick Reference

Given an integer x and a bit position n (0-indexed from LSB):

Check if bit N is set

(x >> n) & 1

Returns 1 if bit n is 1, 0 otherwise

Set bit N

x | (1 << n)

Sets bit n to 1 regardless of current value

Clear bit N

x & ~(1 << n)

Sets bit n to 0

Toggle bit N

x ^ (1 << n)

Flips bit n: 0→1, 1→0

Set bits in mask M

x | M

Sets all bits where M has a 1

Clear bits in mask M

x & ~M

Clears all bits where M has a 1

Toggle bits in mask M

x ^ M

Flips all bits where M has a 1

Get lowest set bit

x & -x

Isolates the rightmost 1 bit

Common Patterns & Gotchas

Power of 2

int isPowerOfTwo(int x) { return x > 0 && (x & (x - 1)) == 0; }

Any power of 2 has exactly one bit set. Subtracting 1 flips all lower bits, so AND gives zero. Works for 1, 2, 4, 8, 16…

Count set bits (Brian Kernighan's method)

int countBits(int x) { int count = 0; while (x) { x &= x - 1; count++; } return count; }

Each iteration clears the lowest set bit. Runs in O(number of set bits) — efficient for sparse numbers.

Swap two integers without a temporary

a ^= b; b ^= a; a ^= b;

XOR swap. Works because x ^ x = 0 and XOR is associative. Gotcha Does not work if a and b reference the same memory location (both become 0).

Check if integers have opposite signs

(a ^ b) < 0

The MSB is the sign bit. If a and b have different signs, XOR yields a negative result. Faster than (a < 0) != (b < 0).

Absolute value without branching

mask = x >> 31; (x + mask) ^ mask;

Also known as "branchless abs". mask is all 1s for negative x, all 0s for positive. Works for 32-bit signed integers.

Round up to next power of 2

x--; x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x++;

Propagates the highest set bit to all lower bits, then adds 1. Returns 0 for x=0 (watch out). 32-bit

Extract the Nth byte from a word

(x >> (n * 8)) & 0xFF

n=0 gives the least significant byte, n=3 gives the most significant (on a 32-bit word).

Two's Complement Note

All these examples assume two's complement representation, which is what most modern hardware and all mainstream languages (C, C++, Java, Rust, Go, Python) use. In two's complement: