Isolate and strip bits

Overview

Two closely related identities let you walk the set bits of a value one at a time. x & (x - 1) strips the lowest set bit, and x & -x isolates it — producing a value with only that one bit remaining. They are complements: strip removes it, isolate keeps only it. Together they give you an iteration idiom that visits exactly the set bits and nothing else: isolate to get the current bit, strip to advance. The isolate identity depends on two's-complement negation, so it is worth understanding why -x produces the mask it does rather than memorising it blindly.

Why it matters

Iterating set bits is how you turn a bitmask back into a list of items: which interrupts fired, which pieces sit on which squares, which options a caller passed. Doing it by testing all 32 positions costs 32 steps every time; the isolate-and-strip loop costs one step per set bit. On a sparse mask — the common case — that is the difference between a hot loop and a bottleneck.

Core concepts

Two's-complement negation. -x equals ~x + 1. Inverting flips every bit; adding one propagates a carry up through the trailing 1s (which were the trailing 0s of x) until it lands on the lowest set bit. The result: -x agrees with ~x above the lowest set bit, and matches x at and below it.

x & -x isolates. ANDing those two leaves exactly the lowest set bit. 0b1100 & -0b1100 → 0b0100.

Write it as x & (0u - x). On unsigned types, negating with a unary minus can trip -Wsign-conversion and looks alarming in review; 0u - x is the same well-defined wrap-around and states the intent.

x & (x - 1) strips. As in the popcount lesson, this clears the lowest set bit and leaves the rest.

The iteration idiom. while (x) { unsigned bit = x & (0u - x); /* use bit */ x &= x - 1u; } visits each set bit once, lowest first. Pair it with a count-trailing-zeros to recover the bit index rather than the bit value.

Syntax notes

unsigned isolate_lowest_set(unsigned x) { return x & (0u - x); }  // keep only lowest set bit
unsigned clear_lowest_set  (unsigned x) { return x & (x - 1u); }  // remove lowest set bit

/* visit each set bit exactly once */
for (unsigned t = mask; t; t &= t - 1u) {
    unsigned bit = t & (0u - t);   // e.g. 0b00000100
    /* ... handle this bit ... */
}

Key points:

• 0u - x rather than -x keeps the expression unsigned and warning-free.
• Both identities return 0 for x == 0, so the loop terminates naturally.
• Isolate gives you the value of the bit; converting to an index needs a trailing-zero count.

Lesson

Two classic tricks operate on the least-significant 1 bit: x & -x isolates it (keeps only that bit), and x & (x-1) strips it (clears it). Strip-in-a-loop visits each set bit exactly once — Kernighan's popcount.

The demo shows both and counts bits by stripping.

Code examples

#include <stdio.h>
static unsigned isolate_lowest_set(unsigned x){ return x & (0u - x); }
static unsigned clear_lowest_set(unsigned x){ return x & (x - 1u); }
int main(void){
    unsigned x = 0x2C;                       /* 0010 1100 */
    printf("x                 = 0x%02X\n", x);
    printf("isolate lowest 1  = 0x%02X\n", isolate_lowest_set(x));
    printf("strip   lowest 1  = 0x%02X\n", clear_lowest_set(x));
    /* Kernighan: strip until zero counts the set bits */
    int n=0; for(unsigned y=x; y; y=clear_lowest_set(y)) n++;
    printf("set bits (strip loop) = %d\n", n);
    return 0;
}

Line by line

Common mistakes

Doing arithmetic negation on a signed type; confusing isolate with strip.

Debugging tips

Compiler errors and warnings:

• warning: unary minus operator applied to unsigned type, result still unsigned (MSVC) — harmless but noisy; write 0u - x instead.
• -Wsign-conversion complaints when mixing -x with signed variables; keep the whole expression unsigned.

Runtime symptoms:

• Undefined behaviour on the most negative value. You applied -x to a signed int holding INT_MIN; negating it overflows. Use unsigned types.
• The loop never ends. You isolated but forgot to strip — the loop variable must advance with t &= t - 1u.
• You get bit values where you wanted indices. x & -x yields 4, not 2. Convert with a trailing-zero count.
• Result is 0 for a non-zero input. You applied the identities to the wrong variable, or stripped before isolating.

Technique: print x, -x and x & -x in binary side by side once — the carry propagation becomes obvious and the identity stops feeling like magic.

Memory safety

• Signed negation overflow. -x where x is a signed INT_MIN is undefined behaviour. This is the one genuine UB trap in this lesson; using unsigned/uint32_t removes it entirely.
• Unsigned wrap is defined. 0u - x and x - 1u on unsigned types wrap modulo 2³², which is exactly what these identities rely on. That behaviour is guaranteed by the standard, not luck.
• Zero input. Both helpers return 0 for 0, so loops terminate; but if you use the isolated bit as a shift amount or array index, handle the zero case before indexing.
• Index conversion. Converting an isolated bit to an index via a loop is fine; via __builtin_ctz is a compiler extension whose behaviour is undefined for zero — guard it.

Real-world uses

Concrete uses: An interrupt handler reads a pending-mask register and services each set bit in turn. A chess engine iterates the squares of a bitboard. A scheduler walks a CPU-affinity mask. A garbage collector walks a mark bitmap. Any API that takes a flags word and must act on each flag passed uses this loop.

Professional best practices:

Beginner:

• Learn the pair together: isolate to read, strip to advance.
• Always work in unsigned.

Intermediate:

• Prefer the isolate/strip loop to a 32-iteration scan whenever masks are sparse.
• Wrap the idiom in a small for_each_set_bit-style macro or helper so the intent is visible and the loop cannot be written wrong twice.
• If you use __builtin_ctz for the index, guard the zero case explicitly — it is undefined there.

Practice tasks

1. (Beginner) Isolate and strip. Implement unsigned isolate_lowest_set(unsigned x) and unsigned clear_lowest_set(unsigned x). Example: for 12: isolate → 4, strip → 8. Concepts: x & -x, x & (x-1).

2. (Beginner) Show the negation. Print x, ~x, -x and x & -x in binary for 12, 1, 0x80000000. Concepts: two's complement, carry propagation.

3. (Intermediate) Iterate set bits. Write void for_each_set_bit(unsigned mask) printing the index of every set bit, lowest first. Hint: isolate, count trailing zeros to get the index, then strip. Example: 0b1010 → 1 3. Concepts: the iteration idiom.

4. (Intermediate) Count iterations. Compare the number of loop iterations for 0x80000000 using a 32-position scan versus isolate-and-strip. Concepts: why sparse masks favour this idiom.

Summary

x & -x isolates the lowest set bit and x & (x - 1) strips it — complements that come straight from two's-complement negation (-x == ~x + 1). Together they give the canonical loop for visiting each set bit exactly once, costing one iteration per set bit rather than one per bit position. Write the negation as 0u - x to keep the expression unsigned and warning-free, never apply unary minus to a signed value that could be INT_MIN, and remember that isolate yields the bit's value — converting to an index needs a trailing-zero count.

Practice with these exercises

• Isolate the lowest set bit
• Strip the lowest set bit