Essential Bit Manipulation Tricks

March 2026 · 32 min read

These are the fundamental building blocks you will use over and over. Every trick here operates in O(1) time with a single or very few CPU instructions. Memorize these and they become second nature.

Trick 1: Set Bit i

Force bit at position i to 1, leaving all other bits unchanged.

x = x | (1 << i);
// or equivalently:
x |= (1 << i);

// Example: set bit 3 of 0b00000010 (2)
//   1 << 3      = 0b00001000
//   0b00000010
// | 0b00001000
// = 0b00001010   (10)

Why it works: 1 << i creates a number with only bit i set. OR-ing with this always makes bit i become 1, and OR with 0 leaves other bits unchanged.

Trick 2: Clear Bit i

Force bit at position i to 0, leaving everything else unchanged.

x = x & ~(1 << i);
// or:
x &= ~(1 << i);

// Example: clear bit 1 of 0b00001010 (10)
//   1 << 1      = 0b00000010
//  ~(1 << 1)    = 0b11111101
//   0b00001010
// & 0b11111101
// = 0b00001000   (8)

Why it works: ~(1 << i) is all 1s except at position i. AND-ing with this preserves every bit except position i, which becomes 0.

Trick 3: Toggle Bit i

Flip bit i: if it is 0 make it 1, if it is 1 make it 0.

x = x ^ (1 << i);
// or:
x ^= (1 << i);

// Example: toggle bit 3 of 0b00001010 (10)
//   0b00001010
// ^ 0b00001000
// = 0b00000010   (2)
// Toggle again: 0b00000010 ^ 0b00001000 = 0b00001010 (10) — back!

Why it works: XOR with 1 flips the bit, XOR with 0 leaves it unchanged. Since the mask has 1 only at position i, only that bit flips.

Trick 4: Check if Bit i is Set

bool isSet = (x >> i) & 1;
// or equivalently:
bool isSet = (x & (1 << i)) != 0;

// Example: check bit 3 of 0b00001010 (10)
// Method 1: (10 >> 3) & 1 = 0b00000001 & 1 = 1 (set!)
// Method 2: 10 & (1 << 3) = 0b00001010 & 0b00001000 = 0b00001000 (nonzero = set)

Trick 5: Isolate the Lowest Set Bit

Extract the rightmost 1-bit, turning off all other bits.

int lowest = x & (-x);

// Example: x = 0b01101000 (104)
//  -x = 0b10011000     (two's complement)
//   x & (-x) = 0b00001000  (8)
//   The lowest set bit is at position 3 (value 8)

Why it works: -x = ~x + 1. The NOT flips all bits, and adding 1 flips them back from the right until the first 0 (which was the first 1 in x). At that position, both x and -x have a 1. All lower positions are 0 in x and 0 in -x. All higher positions are opposite between x and -x. So AND produces only the lowest set bit.

Trick 6: Clear the Lowest Set Bit

x = x & (x - 1);

// Example: x = 0b01101000 (104)
//   x - 1 = 0b01100111
//   x & (x-1) = 0b01100000 (96)
//   Bit 3 (the lowest set bit) is now cleared

Why it works: Subtracting 1 flips the lowest set bit and all bits below it. AND-ing with x turns off the lowest set bit while preserving everything above.

This is the core of Brian Kernighan's bit counting algorithm, which we cover in the Counting Bits post.

Trick 7: Is x a Power of Two?

bool isPow2 = x && !(x & (x - 1));

// Powers of 2 have exactly ONE bit set:
//   1 = 0b0001, 2 = 0b0010, 4 = 0b0100, 8 = 0b1000
// x & (x-1) clears that one bit, giving 0.
// Non-powers have multiple bits, so clearing one still leaves others.

// Edge case: x = 0 is not a power of 2 (hence the x && check)

Trick 8: Swap Without a Temporary

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

// Step by step (a=5, b=3):
// a = 5 ^ 3 = 6         (a now holds XOR of both)
// b = 6 ^ 3 = 5         (b recovers original a)
// a = 6 ^ 5 = 3         (a recovers original b)

// WARNING: fails if a and b refer to the same memory location!
// In practice, just use std::swap. This is a fun trick, not production code.

Trick 9: Check Even or Odd

bool isOdd  = x & 1;     // last bit is 1 for odd numbers
bool isEven = !(x & 1);  // last bit is 0 for even numbers

// Faster than x % 2 (many compilers optimize x % 2 to this anyway)

Trick 10: Turn Off the Rightmost Contiguous 1s

// Turn off the rightmost group of consecutive 1s:
x = ((x | (x - 1)) + 1) & x;

// Example: x = 0b01101100
// x - 1   = 0b01101011
// x|(x-1) = 0b01101111
// +1       = 0b01110000
// & x      = 0b01100000

Trick 11: Multiply/Divide by Powers of 2

x << 1;   // x * 2
x << 3;   // x * 8
x >> 1;   // x / 2 (floor division)
x >> 4;   // x / 16

// Combine for arbitrary multiplications:
// x * 10 = x * 8 + x * 2 = (x << 3) + (x << 1)

Trick 12: Absolute Value Without Branching

int abs_val(int x) {
    int mask = x >> 31;  // all 0s if positive, all 1s if negative
    return (x + mask) ^ mask;
}
// If x >= 0: mask = 0, result = (x + 0) ^ 0 = x
// If x < 0:  mask = -1, result = (x - 1) ^ (-1) = ~(x - 1) = -x

Trick 13: Min/Max Without Branching

int bit_min(int a, int b) {
    return b ^ ((a ^ b) & -(a < b));
}
int bit_max(int a, int b) {
    return a ^ ((a ^ b) & -(a < b));
}

Trick 14: More CP-Essential Tricks

Patterns you will reach for constantly in competitive programming. Memorize the formulas; the derivations are short.

Lowest unset bit

int lowestUnset = (n + 1) & ~n;

// n      = 0b01101011
// n + 1  = 0b01101100
// ~n     = 0b10010100
// (n+1) & ~n = 0b00000100  → bit 2 was the lowest 0

Why: n+1 flips the trailing 1s and the first 0. AND with ~n keeps only that newly turned-on bit.

Iterate over set bits (one bit per iteration)

int n = 0b10110100;
while (n) {
    int b = n & -n;          // isolate the lowest set bit
    int idx = __builtin_ctz(b); // its position
    // ... process bit at idx ...
    n ^= b;                  // clear it and continue
}
// O(popcount(n)) iterations, much faster than scanning all 32 bits
// when n is sparse.

Iterate over all subsets of a mask

// Visit every sub ⊆ m exactly once (sub = 0 is excluded by sub != 0):
for (int sub = m; sub; sub = (sub - 1) & m) {
    // use sub
}
// Include sub = 0:
int sub = m;
do { /* use sub */ sub = (sub - 1) & m; } while (sub != m);

// Total work over all masks of an n-bit universe is O(3^n), not O(4^n),
// because each pair (sub, mask) with sub ⊆ mask is counted once.

This is the workhorse of subset-DP / SOS-DP problems — see the Bitmask DP post.

Set lowest k bits to 0 / 1

int clearLowK = n & ~((1 << k) - 1);   // zero out bits 0..k-1
int setLowK   = n |  ((1 << k) - 1);   // force bits 0..k-1 to 1

// Useful for:
//   - Aligning a value down to a multiple of 2^k (clearLowK)
//   - Building bitmasks for the "first k indices" (setLowK)

Sign function without branching

// Returns -1, 0, or +1 for negative, zero, positive x.
int sgn = (x > 0) - (x < 0);
// Pure bit-trick variant (32-bit signed):
int sgnBit = (x >> 31) | ((unsigned)-x >> 31);
// Or, the textbook one-liner using !!:
int sgn2 = (x >> 31) | (!!x);

Detect that two ints have opposite signs

bool oppositeSigns = (x ^ y) < 0;
// XOR's sign bit is 1 iff x and y have different sign bits.
// Avoids the overflow risk of (x < 0) != (y < 0) ? — well, no overflow either way,
// but the XOR form is one instruction.

Round up to the next multiple of a power of two

// a must be a power of two:
int up = (x + (a - 1)) & ~(a - 1);

// Example: round 13 up to next multiple of 8
//   13 + 7 = 20 = 0b10100
//   ~(8-1) = ~0b00111 = 0b...11000
//   0b10100 & 0b11000 = 0b10000 = 16  ✓

Constantly useful for memory alignment, page-rounding, and fitting items into power-of-two buckets.

Min/max without branching (alternate form)

// Same idea as Trick 13, written compactly:
int mn = y ^ ((x ^ y) & -(x < y));
int mx = x ^ ((x ^ y) & -(x < y));
// -(x < y) is 0 or -1 (all-ones) — it gates the swap mask (x ^ y).

Summary

• Set bit: x | (1 << i)
• Clear bit: x & ~(1 << i)
• Toggle bit: x ^ (1 << i)
• Check bit: (x >> i) & 1
• Isolate lowest set bit: x & (-x)
• Clear lowest set bit: x & (x - 1)
• Power of 2 check: x && !(x & (x - 1))
• These are the atoms of bit manipulation. Every advanced technique builds on these primitives.

Trick Test

Drill the tricks. Each prompt shows an expression or goal; pick the option that describes (or accomplishes) it. The bank focuses on the behavior of the 14 essential tricks plus a few CP-essential follow-ups. Random order each run; Reset reshuffles.

Practice Problems

Direct applications of the tricks above. Solve them with bit-ops first; resort to higher-level reasoning only if the bit form is unclear.

1. LC 191 — Number of 1 Bits easy Kernighan or popcount.
2. LC 136 — Single Number easy XOR fold.
3. LC 260 — Single Number III medium XOR + lowest set bit (n & -n) to partition.
4. LC 137 — Single Number II medium bit-by-bit mod 3 counter.
5. LC 78 — Subsets medium bitmask iteration 0..(1<<n)-1.
6. LC 89 — Gray Code medium i ^ (i >> 1).
7. LC 868 — Binary Gap easy iterate set bits via n & -n.
8. LC 318 — Maximum Product of Word Lengths medium 26-bit char masks; pair with AND==0.
9. LC 187 — Repeated DNA Sequences medium 2-bits-per-base rolling hash.
10. LC 421 — Maximum XOR of Two Numbers medium greedy bit + hashset, or trie.
11. CSES — Bit Strings easy fast modular exponentiation; warms up the binary view.
12. Codeforces 1556D — Take a Guess hard recover values from AND/OR sums via bit identities.