How Two’s Complement Isolates the Lowest Set Bit

In computer science, isolating the lowest set bit of an integer is commonly achieved using the bitwise expression x & (-x). This operation relies fundamentally on the two’s complement system, where a number is negated by flipping all of its bits and adding one. This article explains the underlying binary arithmetic of two’s complement and demonstrates step-by-step why the inversion and increment process uniquely preserves the least significant bit while allowing all other bits to be cancelled out.

The Structure of a Binary Integer

Any non-zero binary integer \(x\) can be broken down into three distinct sections: 1. An arbitrary prefix of higher-order bits. 2. The lowest (least significant) set bit, which is a 1. 3. A suffix of \(k\) trailing zeros (where \(k \ge 0\)).

Represented generically, the number looks like: \[x = \text{[prefix]} \, 1 \, \underbrace{00\dots0}_{k\text{ zeros}}\]

Step 1: Inverting the Bits (One’s Complement)

When all bits of \(x\) are flipped using the bitwise NOT operation (~x), each section of the binary representation changes: * Every bit in the prefix is inverted to its opposite value (\(\sim\text{[prefix]}\)). * The lowest set bit 1 becomes a 0. * All \(k\) trailing zeros become \(k\) trailing ones.

The inverted number is structured as: \[\sim x = \sim\text{[prefix]} \, 0 \, \underbrace{11\dots1}_{k\text{ ones}}\]

Step 2: Adding One (Two’s Complement Negation)

In the two’s complement system, the arithmetic negative \(-x\) is defined as \(\sim x + 1\). Adding \(1\) to \(\sim x\) triggers a ripple-carry effect across the trailing ones: * The \(k\) trailing ones (\(11\dots1\)) plus \(1\) roll over completely, turning back into \(k\) trailing zeros (\(00\dots0\)). * The carry bit propagates to the position of the former lowest set bit, changing that 0 back into a 1. * Because 0 + 1 = 1 generates no further carry, the addition stops immediately. The inverted prefix (\(\sim\text{[prefix]}\)) remains completely untouched.

The resulting negated value is: \[-x = \sim\text{[prefix]} \, 1 \, \underbrace{00\dots0}_{k\text{ zeros}}\]

Step 3: Isolating the Bit with Bitwise AND

When performing a bitwise AND between the original number \(x\) and its two’s complement negation \(-x\), the three sections interact as follows:

• The Prefix: The original prefix is combined with its inverted counterpart (\(\text{[prefix]} \ \& \ \sim\text{[prefix]}\)). Since a bit and its complement never share a 1, this entire region evaluates to 0.
• The Trailing Suffix: The trailing zeros in both numbers (\(00\dots0 \ \& \ 00\dots0\)) evaluate to 0.
• The Lowest Set Bit: Both \(x\) and \(-x\) possess a 1 at the exact same position (\(1 \ \& \ 1\)), which evaluates to 1.

Consequently, every bit in the result is cleared except for the lowest set bit of the original number. Flipping the bits creates the complementary state needed to zero out the prefix, while adding one resets the trailing bits and restores the target 1 via carry propagation.