Essential Bit Tricks

Essential Bit Tricks

An int is an array of 32 bits that the CPU manipulates in a single instruction. Once you stop reading it as a number and start reading it as that array, a small toolkit of one-line idioms replaces whole loops. This page is that toolkit — every trick with the proof of why it works, not just the recipe, because in an interview you will be asked "why", and a memorized incantation collapses under one follow-up.

We build up in two layers. First, addressing a single named bit (test / set / clear / toggle). Then the two idioms that operate on the lowest set bit without knowing where it is — x & (x-1) and x & -x — which are the engine behind power-of-two checks, set-bit counting, and half the bit problems you will ever see.

Layer 1 — addressing a single bit

To touch bit i (counting from 0 at the least-significant end) you first build a mask that has a 1 in exactly that position: 1 << i. Everything else is combining that mask with the right operator, chosen for what it leaves unchanged:

The pattern is the same each time: put the action bit in the mask, and pick the operator whose identity element (the value that leaves a bit untouched) is what fills the rest of the mask. That is the whole idea — the operator you choose is dictated by what you need to preserve.

Traced on x = 10 = 0b1010:

Layer 2 — x & (x - 1): clear the lowest set bit

This single expression turns off the rightmost 1 in x and leaves every other bit alone — without you knowing where that 1 is. Here is why, and the proof is just how subtracting 1 borrows.

Write x as "some high bits, then its lowest 1, then a run of t trailing zeros": x = H 1 000…0. Subtracting 1 has to borrow across those trailing zeros: each 0 becomes 1, the borrow stops at the lowest 1 which becomes 0, and the high part H is untouched. So x-1 = H 0 111…1. Now AND them column by column:

• High bits (H): identical in both → unchanged.
• The lowest set bit: 1 in x, 0 in x-1 → becomes 0 (cleared).
• Trailing zeros: 0 in x, 1 in x-1 → stay 0.

Net effect: exactly the lowest set bit is cleared. Traced on x = 12 (an 8-bit window shown; the real word is 32 bits, all-zero above):

The lowest set bit (value 4, at position 2) is gone; the higher 1 (value 8) survives. Iterate this and you strip the 1s one at a time from the bottom — which is exactly how we count them below.

Layer 2 — x & -x: isolate the lowest set bit

The mirror trick: this yields a value with only the lowest set bit of x on, and every other bit off (it returns 0 when x is 0). The proof rests on how two's complement builds a negative: -x = ~x + 1.

Take the same shape x = H 1 000…0 (lowest set bit at position p, then p trailing zeros). Flipping gives ~x = ¬H 0 111…1. Adding 1 makes the p trailing ones roll over to zeros with a carry into position p, turning it to 1; the high part becomes ¬H. So -x = ¬H 1 000…0. Now AND with x:

• High bits: H vs its complement ¬H → every column is 1&0 or 0&1 = 0.
• Position p: 1 in both → 1.
• Trailing zeros: 0 in both → 0.

Only position p survives. Traced on x = 12 (8-bit window; the leading 1s of a negative fill all 32 bits):

Result 4 = the lowest set bit's value. This is the trick behind Fenwick (Binary Indexed) trees and behind isolating a "differentiating bit" in Single Number III.

The idioms these unlock

Power-of-two check. A positive power of two has exactly one set bit, so clearing that one bit leaves 0:

isPowerOfTwo(x) = (x > 0) && ((x & (x - 1)) == 0)

The x > 0 guard matters: for x = 0, x & (x-1) = 0 & -1 = 0 would wrongly report "power of two", and negatives are never powers of two. Check: 16 = 10000, 16 & 15 = 10000 & 01111 = 0 → true. 12 = 1100, 12 & 11 = 1000 ≠ 0 → false.

Count set bits (Kernighan). Since x & (x-1) removes one set bit per application, loop until x is 0 and count the iterations — the loop runs once per set bit, not once per bit-width. Traced on x = 13 = 0b1101 (3 set bits → 3 iterations):

Low-k-bits mask. (1 << k) - 1 is k ones. 1 << k is a single 1 at position k (value 2^k); subtracting 1 borrows it down into k trailing ones. Example: (1 << 5) - 1 = 32 - 1 = 31 = 0b11111. Use it to keep only the low k bits of a value: x & ((1 << k) - 1).

Java: the bit-trick toolkit

public class BitTricks {

    static int  getBit(int x, int i)     { return (x >> i) & 1; }
    static int  setBit(int x, int i)     { return x | (1 << i); }
    static int  clearBit(int x, int i)   { return x & ~(1 << i); }
    static int  toggleBit(int x, int i)  { return x ^ (1 << i); }

    static int  clearLowest(int x)       { return x & (x - 1); }   // drop rightmost 1
    static int  lowestBit(int x)         { return x & -x; }        // isolate rightmost 1
    static boolean isPowerOfTwo(int x)   { return x > 0 && (x & (x - 1)) == 0; }
    static int  lowMask(int k)           { return (1 << k) - 1; }  // k low ones

    static int popcount(int x) {          // Kernighan: one pass per set bit
        int count = 0;
        while (x != 0) { x &= (x - 1); count++; }
        return count;
    }

    public static void main(String[] args) {
        int x = 0b1010;                   // 10
        System.out.println(getBit(x, 1));       // 1
        System.out.println(setBit(x, 0));       // 11
        System.out.println(clearBit(x, 1));     // 8
        System.out.println(toggleBit(x, 3));    // 2
        System.out.println(clearLowest(12));    // 8
        System.out.println(lowestBit(12));      // 4
        System.out.println(isPowerOfTwo(16));   // true
        System.out.println(isPowerOfTwo(12));   // false
        System.out.println(popcount(13));       // 3
        System.out.println(lowMask(5));         // 31
    }
}

Go: the bit-trick toolkit

package main

import "fmt"

func getBit(x, i int) int    { return (x >> i) & 1 }
func setBit(x, i int) int    { return x | (1 << i) }
func clearBit(x, i int) int  { return x &^ (1 << i) } // &^ is Go's "AND NOT" — no unary ~
func toggleBit(x, i int) int { return x ^ (1 << i) }

func clearLowest(x int) int   { return x & (x - 1) }
func lowestBit(x int) int     { return x & -x }
func isPowerOfTwo(x int) bool { return x > 0 && x&(x-1) == 0 }
func lowMask(k int) int       { return (1 << k) - 1 }

func popcount(x int) int {     // Kernighan: one pass per set bit
	count := 0
	for x != 0 {
		x &= x - 1
		count++
	}
	return count
}

func main() {
	x := 0b1010 // 10
	fmt.Println(getBit(x, 1))     // 1
	fmt.Println(setBit(x, 0))     // 11
	fmt.Println(clearBit(x, 1))   // 8
	fmt.Println(toggleBit(x, 3))  // 2
	fmt.Println(clearLowest(12))  // 8
	fmt.Println(lowestBit(12))    // 4
	fmt.Println(isPowerOfTwo(16)) // true
	fmt.Println(isPowerOfTwo(12)) // false
	fmt.Println(popcount(13))     // 3
	fmt.Println(lowMask(5))       // 31
}

Traps that bite in the room

• Java has no unsigned ~ problem, but Go has no unary ~ at all. Go writes bitwise NOT as the unary ^ (so ^(1<<i)), and offers the dedicated AND-NOT operator &^ for "clear these bits". The idiomatic clear-bit in Go is x &^ (1 << i) — use it and you never type a NOT.
• 1 << i is an int shift, and int is 32 bits in Java. If you need bit 31 or beyond — or bit positions up to 63 — shift a long: 1L << i. 1 << 31 in Java is the sign bit (a negative number, -2147483648), and 1 << 32 does not overflow to 0: Java masks the shift count mod 32, so 1 << 32 == 1 << 0 == 1 — a silent, easy-to-miss bug. Go's int is 64-bit on modern platforms, so it tolerates larger positions but a shift count ≥ the type width yields 0 (Go does not mask the count).
• x & -x and negatives. The isolate-lowest-bit trick is defined by two's complement, so it works for negative x too — but -x overflows for Integer.MIN_VALUE (-x == x there), and x & -x then returns MIN_VALUE itself, which is correct (its only set bit is the sign bit) yet surprising. Know it before you assert an answer.
• Shift by a negative or out-of-range amount is a bug, not a no-op. Never let i come from untrusted arithmetic without a range check.

When to reach for these — and when not

• x & (x-1) for popcount vs a builtin. In production, call Integer.bitCount(x) (Java) or bits.OnesCount(uint(x)) (Go) — both compile to a single POPCNT instruction and are faster and clearer than the loop. Reach for the Kernighan loop when you must explain popcount in an interview, or on a platform without the intrinsic. The loop's edge is that it runs in set-bit count, not bit-width, so it is cheap for sparse words.
• Single-bit idioms vs a boolean array / BitSet. Packing flags into an int is worth it when the set is small (≤ 32/64 members), fixed, and you want cheap set-algebra (union = |, intersection = &) or a compact map key. For a large or unbounded set, or when readability matters more than the constant factor, use a real boolean[] / BitSet / map — the packed int saves memory and enables O(1) whole-set ops, at the cost of readability and a hard size ceiling.
• Power-of-two check vs Math.log. The bit test is exact and integer-only; a floating log2 round-trip risks precision error at large values. Prefer x & (x-1) whenever the input is an integer.

Takeaways

• Pick the operator by its identity element: OR to set, AND with a NOT-mask to clear, XOR to toggle, all against 1 << i.
• x & (x-1) clears the lowest set bit (proof: how borrow works); x & -x isolates it (proof: -x = ~x + 1).
• Those two build power-of-two checks, Kernighan popcount (loops per set bit), and low-k-bit masks with (1<<k)-1.
• Watch bit width: shift a long / 1L past bit 30, and remember Go clears bits with &^, not ~.