Bit Manipulation Identities

May 2026 · 24 min read

Bit manipulation becomes powerful when you stop memorizing isolated tricks and start seeing identities. These formulas are the algebra of bit patterns: they let you isolate structure, clear structure, build masks, and reason about carries without simulating arithmetic digit by digit.

Identity Cheat Sheet

Expression	Name	Meaning
`x & -x`	lowbit	Isolates the lowest set bit.
`x & (x - 1)`	clear lowbit	Turns off the lowest set bit.
`x \| (x - 1)`	fill below lowbit	Turns all bits below the lowest set bit into 1.
`x ^ (x - 1)`	low mask	Creates a mask from bit 0 through the lowest set bit.
`~x`	complement	Flips every bit in the fixed-width representation.
`~x == -x - 1`	two's complement identity	Connects NOT and negation.
`x & y`	intersection	Bits set in both values.
`x \| y`	union	Bits set in either value.
`x ^ y`	symmetric difference	Bits set in exactly one value.

Why `x & -x` Works

In two's complement, -x is ~x + 1. The addition flips all trailing zeros to zeros again and keeps the lowest set bit aligned. Everything above that bit differs enough that the AND removes it.

x    = 0b10110100
~x   = 0b01001011
-x   = 0b01001100
x&-x = 0b00000100

The result is a power of two representing the lowest set bit. This is why Fenwick trees use i += i & -i and i -= i & -i.

Clearing Bits

Subtracting 1 from a number flips the lowest set bit to 0 and turns every bit below it into 1. ANDing that with the original number clears exactly that lowest set bit.

x       = 0b10110100
x - 1   = 0b10110011
x&(x-1) = 0b10110000

Repeatedly applying this identity loops only over set bits:

int count_bits(unsigned x) {
    int ans = 0;
    while (x) {
        x &= x - 1;
        ++ans;
    }
    return ans;
}

Mask Identities

// Lower k bits set.
uint64_t low = (1ULL << k) - 1;

// Bits l..r set, inclusive.
uint64_t range = ((1ULL << (r - l + 1)) - 1) << l;

// Clear bits l..r in x.
x &= ~range;

// Replace bits l..r with value v.
x = (x & ~range) | ((v << l) & range);

Carry Intuition

XOR adds bits without carrying. AND finds the positions where a carry is created. Shift those carries left by one and repeat.

int add(int a, int b) {
    while (b != 0) {
        int carry = (unsigned)(a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

This is not usually better than +, but it is an interview-quality proof that you understand binary addition.

De Morgan's Laws for Bits

~(a & b) == (~a | ~b)
~(a | b) == (~a & ~b)

These are useful when turning "avoid these bits" constraints into masks. They also explain how CPU instruction sets can synthesize one operation from others.

Pitfalls

~x depends on width. ~0 is all ones for the type, not a mathematical infinity of ones.
x & -x is cleanest on unsigned values, especially around signed overflow edge cases.
(1 << k) - 1 is unsafe when k is the width of the type. Handle full masks separately.

Identity Test

Quiz yourself on the cheat sheet. You're given the meaning; pick the matching expression. The bank covers everything on this page plus the most common derived idioms from Essential Tricks. Questions are drawn in a random order; Reset reshuffles the bank.

Practice Problems

LeetCode 191 - Number of 1 Bits clear lowbit use x &= x - 1.
LeetCode 260 - Single Number III lowbit split values by the lowest differing bit.
LeetCode 371 - Sum of Two Integers carry XOR plus shifted AND.
LeetCode 201 - Bitwise AND of Numbers Range common prefix repeatedly clear low bits or shift prefixes.