Book contents
Contents
raw Math
RAW Book Algorithms Bit Manipulation

Introduction to Bit Manipulation Tricks

Robert Eisele

Bit manipulation tricks exploit the two's complement binary representation of integers to perform common tasks, such as testing, isolating, or counting bits, with compact combinations of arithmetic and bitwise operators. They show up in low-level performance code, hashing, graphics, and compression, and many of them rely on nothing more than the identities of modular arithmetic applied to base 2.

Setting a Variable to Zero

A value can be cleared with a self-XOR instead of an explicit assignment: 

a ^= a;

This works because XOR-ing any bit pattern with itself cancels every bit, \(x\oplus x=0\), regardless of the value stored in \(a\). Historically this was a few bytes smaller than loading the immediate value \(0\) on some instruction sets, though modern compilers already emit the shortest zeroing instruction for a plain a = 0;, so the trick is mostly of historical and educational interest today. It also only makes sense for integer types: applying it to a floating-point NaN still yields \(0\), since the trick operates on the raw bit pattern of the register, not on the arithmetic value.

Isolating the Lowest Set Bit

lowest = v & -v;

In two's complement, \(-v\) is computed as \(\lnot v+1\). Let \(v\) end in \(k\) trailing zero bits followed by a \(1\). Complementing flips every bit, so \(\lnot v\) ends in \(k\) trailing one bits followed by a \(0\); adding \(1\) then carries through those \(k\) ones, turning them back into zeros and setting the bit at position \(k\), while every higher bit of \(\lnot v+1\) is the complement of the corresponding bit of \(v\). Only at position \(k\) do \(v\) and \(-v\) agree with a \(1\); ANDing them together therefore keeps exactly that one bit and clears everything else.

Example: for \(v=0\text{b}00101100\), the lowest set bit is at position \(2\), and indeed \(v\ \&\ (-v) = 0\text{b}00000100\).

Clearing the Lowest Set Bit

v &= v - 1;

Subtracting \(1\) flips the trailing zero bits to ones and turns the lowest set bit into a zero, leaving every higher bit unchanged. ANDing with the original value \(v\) then keeps all the unaffected higher bits and forces the lowest set bit to \(0\), while the already-flipped trailing bits become \(0\) as well since they no longer match \(v\).

Repeating this operation until \(v\) becomes \(0\) counts the number of set bits, known as the Hamming weight or population count: 

unsigned int c;
for (c = 0; v != 0; ++c) {
  v &= v - 1;
}

This is Brian Kernighan's algorithm: it runs in time proportional to the number of set bits rather than the total bit width, which is faster than testing every bit individually when \(v\) is sparse. Most modern processors also expose a dedicated popcnt instruction that computes this in a single, constant-time step.

Popcount is also the basis of the Hamming distance between two values, popcount(a ^ b): since \(a\oplus b\) has a set bit exactly where \(a\) and \(b\) differ, counting its set bits counts the number of differing bit positions. This is a distinct quantity from the Hamming weight of a single value, even though both are computed with the same popcount routine.

Locating the Next Zero Bit After a Run of Ones

lo   = v & -v;
next = (v + lo) & ~v;

Let the lowest set bit of \(v\) sit at position \(k\), so \(\text{lo}=2^k\), and suppose it is followed by a run of \(r\) consecutive one bits, positions \(k\) through \(k+r-1\), with a zero at position \(k+r\). Adding \(\text{lo}\) to \(v\) triggers a carry that ripples through the entire run: every bit in the run flips from \(1\) to \(0\), and the carry finally sets the first zero bit above the run, at position \(k+r\). Bits below \(k\) and above \(k+r\) are untouched. ANDing the sum with \(\lnot v\) then keeps only the bits where \(v\) was \(0\): every position in the flipped run was \(1\) in \(v\) and is discarded, while position \(k+r\) was \(0\) in \(v\) and survives. The result is exactly \(2^{k+r}\), the lowest zero bit immediately above the run of ones starting at the lowest set bit. This single step is the core building block of algorithms that enumerate all bit patterns with a fixed number of set bits in increasing numeric order.

Testing for a Power of Two

A power of two has exactly one set bit, so clearing its lowest set bit must yield zero: 

bool f = (v & (v - 1)) == 0;

This first form also reports true for \(v=0\), because both operands of the AND are zero. Exclude zero explicitly to obtain the complete test for an unsigned integer: 

bool f = v && !(v & (v - 1));

Testing for a Run of Trailing Ones

A dual question is whether \(v\) consists of a solid run of one bits starting at bit \(0\), that is, \(v=2^{k}-1\) for some \(k\ge 0\) (including \(v=0\) for \(k=0\)). Adding \(1\) to such a value carries through every one bit and produces a single set bit right above the run, with no overlap: 

isTrailingOnes(v) = (v & (v + 1)) == 0

If \(v\) has any zero bit among its low bits, that zero survives untouched in \(v+1\), so it is also a zero in \(v\), and the AND is nonzero. Only when every low bit of \(v\) is \(1\) does the increment clear all of them, leaving no overlap with \(v\) at all.

Swapping Two Variables Without a Temporary

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

Substituting the original values step by step shows why this works. After the first line, \(a=a_0\oplus b_0\). In the second line, \(b=b_0\oplus(a_0\oplus b_0)=a_0\), using \(x\oplus x=0\) and \(x\oplus 0=x\). In the third line, \(a=(a_0\oplus b_0)\oplus a_0=b_0\). So after the three steps, \(a=b_0\) and \(b=a_0\): the values have swapped without ever storing either one in a separate variable.

This relies on \(a\) and \(b\) referring to two distinct memory locations. If \(a\) and \(b\) are the same variable, the very first line computes \(a\oplus a=0\) and both quantities collapse to zero, destroying the value entirely.

Extracting the Sign Bit

For a two's complement integer of \(w\) bits, the most significant bit is \(1\) exactly when the value is negative. An arithmetic right shift by \(w-1\) positions copies that sign bit into every bit of the result: 

sign = v >> (w - 1);   // -1 if v < 0, else 0

Detecting Integers with Opposite Signs

bool oppositeSigns = ((x ^ y) < 0);

XOR sets its most significant bit exactly when the sign bits of x and y differ. Interpreting that XOR result as a signed two's complement integer therefore makes the comparison with zero true precisely when one input is negative and the other is nonnegative. Both operands must have the same signed integer type; unsigned operands never compare less than zero.

Branch-Free Absolute Value

The sign-extension trick above turns absolute value into a two-instruction sequence with no conditional branch: 

mask = v >> (w - 1);
abs  = (v ^ mask) - mask;

If \(v\ge 0\), then \(\text{mask}=0\), so \(\text{abs}=(v\oplus 0)-0=v\), unchanged. If \(v<0\), then \(\text{mask}=-1\), whose bit pattern is all ones; XOR-ing with all ones is exactly bitwise complement, so \(v\oplus\text{mask}=\lnot v\), and \(\text{abs}=\lnot v-(-1)=\lnot v+1=-v\), the two's complement negation of \(v\). Either way the result is \(|v|\), computed without a comparison or a jump.

An equivalent formulation swaps the order of the operations, adding the mask before the XOR instead of after: 

int const mask = v >> (sizeof v * CHAR_BIT - 1);
unsigned int magnitude = (v + mask) ^ mask;

For \(v\ge 0\) this again leaves \(v\) unchanged, and for \(v<0\) it computes \((v-1)\oplus(-1)=\lnot(v-1)=-(v-1)-1=-v\), the same result reached from the other direction.

In C, the compact signed expression has undefined behavior for INT_MIN: its positive magnitude is not representable as an int, and v + mask overflows before assignment to the unsigned result. An unsigned formulation keeps every intermediate operation modulo \(2^w\) and can represent that final magnitude: 

unsigned int bits = (unsigned int)v;
unsigned int mask = 0u - (bits >> (sizeof bits * CHAR_BIT - 1));
unsigned int magnitude = (bits ^ mask) - mask;

Conditionally Negating a Value Without a Branch

A Boolean flag can select between \(v\) and \(-v\) by expanding zero or one into an arithmetic factor. When dontNegate is true, the factor is \(1\); when it is false, the factor is \(-1\): 

int result = (dontNegate ^ (dontNegate - 1)) * v;

Reversing the meaning of the flag gives a more direct two's complement form. For negate = 0, both extra operations are identities. For negate = 1, XOR with \(-1\) complements every bit and adding one completes the negation: 

int result = (v ^ -negate) + negate;

In both forms the flag must be exactly \(0\) or \(1\). As with ordinary signed negation, negating INT_MIN is undefined in C because \(-\text{INT_MIN}\) is not representable as an int.

Testing, Setting, Clearing, and Toggling a Single Bit

A single bit at position \(b\) is addressed through the mask \(1\ll b\). Reading it back out, forcing it to \(1\), forcing it to \(0\), and flipping it are each a one-line combination of shift, AND, OR, and XOR: 

test:   (v >>> b) & 1
set:    v |= (1 << b)
clear:  v &= ~(1 << b)
toggle: v ^= (1 << b)

Testing shifts the target bit down to position \(0\) and masks away everything else; setting ORs in a \(1\) at that position while leaving every other bit untouched, since \(x\vee 0=x\); clearing ANDs with a mask that is \(0\) only at position \(b\), forcing that bit to \(0\) while preserving the rest, since \(x\wedge 1=x\); toggling XORs a single \(1\) bit in, flipping only that position because \(x\oplus 0=x\) everywhere else. Negating an entire word follows the same idea with every bit toggled at once, either as v = ~v or, exploiting that \(-1\) is represented as all one bits, as v ^= -1.

Building a Bit Mask for a Range of Bits

The single-bit operations above generalize to an arbitrary mask: v |= mask sets every bit that is \(1\) in mask, v &= ~mask clears every such bit, and v ^= mask toggles them, by the same per-bit reasoning as above applied simultaneously to every masked position. A mask covering all bits from position \(f\) (inclusive) to \(t\) (inclusive) can be built directly: 

mask = ((2 << (t - f)) - 1) << f

The range contains \(t-f+1\) bits, and a block of that many low bits is \(2^{t-f+1}-1\), written here as \((2\ll(t-f))-1\) to build the value from \(2\) rather than shifting a \(1\) by a full word width, which some platforms treat as undefined. Shifting the resulting low block left by \(f\) then moves it into position.

Selecting Bits with a Branch-Free Multiplexer

Let b be a bit mask and let f be exactly \(0\) or \(1\). The conditional expression below sets every position selected by b when f is \(1\), clears those positions when f is \(0\), and preserves every unselected bit of x: 

f ? (x | b) : (x & ~b)

At a position where \(b=0\), both branches return the original bit of \(x\). Where \(b=1\), the true branch returns \(1\) and the false branch returns \(0\), so that result bit is exactly f. The expression is therefore a bitwise multiplexer: b ? f : x, with the mask selecting independently which bit positions receive the Boolean value.

Two's complement expands the Boolean into a whole-word mask: \(-f\) is all zeros for \(f=0\) and all ones for \(f=1\). That gives the equivalent branch-free form: 

x ^ (b & (x ^ -f))

For \(f=0\), this becomes \(x\oplus(b\land x)=x\land\neg b\). For \(f=1\), it becomes \(x\oplus(b\land\neg x)=x\lor b\). These are exactly the false and true branches above. In JavaScript, bitwise operators coerce values to signed 32-bit integers; append >>> 0 when the same 32-bit pattern should be displayed as an unsigned number.

Conditionally Setting or Clearing Bits Without a Branch

w ^= (-f ^ w) & m;

This is the compound-assignment form of the multiplexer identity with b = m. The flag f must be \(0\) or \(1\): selected bits become \(f\), while every bit outside m passes through unchanged. The equivalent select-and-merge form exposes the two masked inputs separately, which may suit a processor's instruction scheduling better: 

w = (w & ~m) | (-f & m);

To assign just bit \(p\), specialize the mask to 1u << p: 

w ^= (w ^ -f) & (1u << p);

Bit Sets: Union, Intersection, and Difference

An integer can represent a finite subset of \(\{0,1,\dots,w-1\}\) by treating bit \(i\) as the indicator of whether element \(i\) belongs to the set. Because AND, OR, and XOR act independently on every bit position, the standard set operations fall directly out of the bitwise operators: 

union:        A | B
intersection: A & B
difference:   A & ~B

Union sets a bit whenever either input has it, matching \(\lor\); intersection sets a bit only when both inputs have it, matching \(\land\); and difference keeps exactly the bits of \(A\) that are absent from \(B\), since \(\lnot B\) is \(1\) precisely at the positions not in \(B\). This representation also makes enumerating all subsets of an \(n\)-element set straightforward: the integers \(0\) through \(2^n-1\) correspond, bit pattern for bit pattern, to exactly the \(2^n\) distinct subsets.

Rounding Up to the Next Power of Two

uint32_t roundUpPow2(uint32_t v)
{
  --v;
  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;
  return ++v;
}

Subtracting \(1\) first ensures that a \(v\) which is already a power of two maps to itself rather than to the next one up. Each subsequent OR smears the highest set bit downward: after ORing with a shift by \(1\), the top two bits are both \(1\); after shifting by \(2\), the top four bits are \(1\); and so on, doubling the width of the filled region at every step until, for a \(32\)-bit word, all bits from the original highest set bit down to bit \(0\) are \(1\). Adding \(1\) to that solid run of ones then carries all the way up, producing exactly the next power of two.

For this 32-bit version, the defined nonzero result range is \(1\le v\le 2^{31}\). An input of zero underflows on the first line and returns zero after unsigned wraparound; an input above \(2^{31}\) also returns zero because the required next power, \(2^{32}\), does not fit in uint32_t.

Counting Trailing Zeros via Popcount

trailingZeros(v) = popcount((v & -v) - 1)

\(v\ \&\ (-v)\) isolates the lowest set bit, giving exactly \(2^{k}\) where \(k\) is the number of trailing zeros. Subtracting \(1\) from a single set bit at position \(k\) produces a block of \(k\) one bits below it and nothing else, so counting that block's set bits with popcount recovers \(k\) directly.

Summing Repeated Halvings

repeatedHalvingSum(v)
    s = 0
    while (v != 0)
        s = s + v
        v = v / 2
    return s

Writing \(v=\sum_j b_j2^j\) with bits \(b_j\in\{0,1\}\), this loop computes \(\sum_{i\ge 0}\lfloor v/2^i\rfloor\). Swapping the order of summation,

\[ \sum_{i\ge 0}\Big\lfloor\frac{v}{2^i}\Big\rfloor =\sum_{i\ge 0}\sum_{j\ge i}b_j2^{j-i} =\sum_j b_j\sum_{i=0}^{j}2^{j-i} =\sum_j b_j\left(2^{j+1}-1\right) =2\sum_j b_j2^j-\sum_j b_j =2v-\operatorname{popcount}(v), \]

since the inner sum \(\sum_{i=0}^{j}2^{j-i}\) is a geometric series equal to \(2^{j+1}-1\). The entire loop therefore collapses to a single closed-form expression: 

repeatedHalvingSum(v) = 2 * v - popcount(v)

Removing the Lowest Zero Bit

removeLowestZero(v) = (v >> 1) | ((v + 1) >> 1)

Let the lowest zero bit of \(v\) sit at position \(p\); by definition every bit below \(p\) is \(1\). Incrementing \(v\) then carries through those \(p\) low one bits, clearing all of them and setting bit \(p\) to \(1\), while every bit above \(p\) stays the same. Shifting both \(v\) and \(v+1\) right by one and ORing them together reproduces the unchanged low bits, which are \(1\) in both operands below position \(p-1\); at position \(p-1\) itself, \(v\) contributes \(0\) and \(v+1\) contributes \(1\), so the OR is \(1\); and from position \(p\) upward, \(v\) and \(v+1\) agree bit for bit, so the OR simply reproduces \(v\)'s higher bits, shifted down by one. The net effect is that bit \(p\) is deleted from \(v\)'s binary representation and every bit above it collapses down to fill the gap.

Repeating this step once per zero bit, while counting the shifts, packs all of a number's one bits to the top and all its zero bits to the bottom, terminating once the value is a solid run of trailing ones (checked with the trailing-ones test above). The same result can also be built directly from the bit counts alone: with \(o\) one bits and \(z\) zero bits among \(v\)'s significant digits, the canonical arrangement is 

canonical(v) = ((1 << o) - 1) << z

Sign-Extending a k-Bit Two's Complement Value

signExtend(v, k)
    if v < (1 << (k - 1))
        return v
    return v - (1 << k)

When only the lowest \(k\) bits of a value are meaningful, bit \(k-1\) is the sign bit of that narrower representation. If it is \(0\), meaning \(v<2^{k-1}\), the stored bits already equal the intended nonnegative value and no correction is needed. If it is \(1\), the \(k\)-bit two's complement encoding of a negative value \(-m\) stores the bit pattern \(2^k-m\), so \(v=2^k-m\) and the true value is \(-m=v-2^k\), which is exactly the correction applied.

Finding the Position of the Lowest Set Bit via a Floating-Point Exponent

lsbPosition(v)
    f    = (float) (v & -v)
    bits = reinterpretAsUint32(f)
    return (bits >> 23) - 127

As before, \(v\ \&\ (-v)\) isolates the lowest set bit as an exact power of two, \(2^{k}\). Converting an integer power of two to an IEEE‑754 single-precision float produces the normalized value \(1.0\times 2^{k}\), whose \(8\)-bit exponent field stores the biased exponent \(k+127\). Reinterpreting the float's bit pattern as an integer, shifting right by \(23\) to discard the mantissa, and subtracting the bias \(127\) recovers \(k\) directly from the hardware's floating-point conversion, in the same spirit as the exponent manipulation used in the fast inverse square root algorithm.

Common Pitfalls

Key Results

Related Stuff

raw / Algorithms
01 Aug
·
Robert Eisele

Introduction to Bitwise Obfuscation Tricks

This explains bitwise obfuscation tricks through two's-complement arithmetic, XOR equality, and mask identities: incrementing and decrementing through complement, rewriting equality checks through XOR, turning a comparison against a constant into a zero test, building branch-free conditional negation, expanding a boolean flag into a mask, returning only even values, and absorbing a mask into a sub-expression, along with language-specific limitations and readability pitfalls.
raw / Databases
08 Jul
·
Robert Eisele

Set and Clear Bit Flags Atomically in MySQL

A precise derivation of masked bit replacement, branch-free Boolean flag assignment, and separate set-and-clear updates in MySQL. The article proves each expression bit by bit, defines overlap semantics, uses parameterized PDO statements, and covers atomicity, idempotence, unsigned 64-bit limits, and cases where a normalized schema is preferable.
raw / Algorithms
04 Aug
·
Robert Eisele

Introduction to the Quine-McCluskey Algorithm

Derives the Quine-McCluskey algorithm for Boolean minimization, works from grouping through the prime implicant chart and Petrick's method, extends merging to XOR and XNOR logic following Turton (1996), and develops both disjoint-support and Shannon XOR decompositions, including a compact two-to-one multiplexer form.
All Math