Why Subtracting One Flips Binary Bits

In binary arithmetic, subtracting one from an integer flips the lowest set bit (the least significant bit with a value of 1) to zero and transforms all preceding lower-order zeros into ones. This behavior is the foundation of numerous low-level bitwise operations, such as Brian Kernighan’s algorithm for counting set bits. The mathematical explanation behind this phenomenon is rooted in the algebraic identity for a finite geometric series, specifically \(2^k - 1 = \sum_{i=0}^{k-1} 2^i\).

Representing the Binary Number Algebraically

Any non-zero positive binary integer \(N\) can be partitioned based on the position of its lowest set bit. Let \(k\) be the index of this least significant set bit (using zero-based indexing from right to left).

Because bit \(k\) is the lowest set bit: - Bits from index \(0\) to \(k-1\) are all 0. - Bit \(k\) is 1 (contributing \(2^k\) to the value). - Bits from index \(k+1\) onward represent higher-order values.

We can express \(N\) algebraically as: \[N = M \cdot 2^{k+1} + 2^k\]

where \(M\) represents the integer value of all bits above index \(k\).

The Core Algebraic Identity

When subtracting \(1\) from \(N\), the operation applies directly to the \(2^k\) component: \[N - 1 = M \cdot 2^{k+1} + (2^k - 1)\]

The term \((2^k - 1)\) is evaluated using the geometric progression sum identity: \[2^k - 1 = \sum_{i=0}^{k-1} 2^i = 2^{k-1} + 2^{k-2} + \dots + 2^1 + 2^0\]

Bitwise Effect of the Identity

Applying the identity to the equation for \(N - 1\) gives: \[N - 1 = M \cdot 2^{k+1} + \sum_{i=0}^{k-1} 2^i\]

Breaking this down by bit positions reveals why each bit behaves the way it does:

  1. Higher Bits (\(> k\)): The term \(M \cdot 2^{k+1}\) remains unaffected, meaning all bits above index \(k\) stay identical to those in \(N\).
  2. The \(k\)-th Bit: The term \(2^k\) is replaced by the sum of smaller powers of two. Thus, the bit at index \(k\) changes from 1 to 0.
  3. Lower Bits (\(0\) to \(k-1\)): The sum \(\sum_{i=0}^{k-1} 2^i\) fills every power of two from \(0\) up to \(k-1\). Consequently, all bits from index \(0\) to \(k-1\), which were previously 0, become 1.

Example

Consider the binary number 11000 (\(N = 24\)): - Lowest set bit is at \(k = 3\) (\(2^3 = 8\)). - \(N = 1 \cdot 2^4 + 2^3 = 16 + 8 = 24\). - \(N - 1 = 16 + (2^3 - 1) = 16 + (2^2 + 2^1 + 2^0) = 16 + 7 = 23\).

In binary: - \(N = \text{11000}_2\) - \(N - 1 = \text{10111}_2\)

The bit at index 3 flipped from 1 to 0, and indices 0 through 2 flipped from 0 to 1, exactly matching the expansion of \(2^k - 1\).