证明n位字x的x & (x-1)操作会关闭最右侧置位比特

Great question! This is one of those elegant bitwise tricks from Hacker's Delight that feels like magic until you unpack the mechanics. Let’s walk through both a bit-string-based proof (super intuitive for folks who think in binary) and a formal mathematical proof to cover all bases.

Let’s start with how binary numbers behave when you subtract 1—this is the key to understanding the trick:

1. Define the structure of x:
   Suppose x is an n-bit number where the rightmost set bit (1) is at position k (we count positions starting from 0 at the far right). In binary, x looks like this:

   b_{n-1} b_{n-2} ... b_{k+1} 1 0 0 ... 0
   (The 1 is at position k, followed by k zeros.)

2. What happens when we compute x - 1?:
   Subtracting 1 will flip the rightmost set bit from 1 to 0, and flip all the zeros to the right of that bit to 1. This is because we need to borrow 1 from the rightmost 1 to subtract from the trailing zeros. So x - 1 looks like:

   b_{n-1} b_{n-2} ... b_{k+1} 0 1 1 ... 1
   (The 1 at position k becomes 0, and all trailing zeros become 1s.)

3. Compute x & (x - 1):
   When we perform a bitwise AND between x and x-1:

   • All bits to the left of position k are identical in both x and x-1, so they stay the same after the AND.
   • The bit at position k is 1 in x and 0 in x-1—ANDing these gives 0.
   • All bits to the right of position k are 0 in x and 1 in x-1—ANDing these gives 0.

   The result? The rightmost set bit of x is turned off (set to 0), and all other bits remain exactly as they were in x. Perfect match for the example you gave: 0101100 → 0101000.

For a more rigorous take, let’s use number theory:

1. Decompose x:
   Let (2^k) be the largest power of 2 that divides x. This means we can write x as:
   [
   x = m \cdot 2^{k+1} + 2^k
   ]
   where m is a non-negative integer (the "high-order" part of x, left of the rightmost set bit). The term (2^k) represents the rightmost set bit, and (m \cdot 2^{k+1}) ensures there are no set bits to the right of position k.

2. Compute x - 1:
   Subtract 1 from x:
   [
   x - 1 = m \cdot 2^{k+1} + 2^k - 1
   ]
   Notice that (2^k - 1) is a number with k consecutive 1s in binary (e.g., (2^3 -1 = 7 = 111_2)). So x-1 is the high-order part (m \cdot 2^{k+1}) plus k trailing 1s.

3. Compute the bitwise AND:
   The bitwise AND of x and x-1 is equivalent to:
   [
   (m \cdot 2^{k+1} + 2^k) & (m \cdot 2^{k+1} + (2^k - 1))
   ]

   • The term (m \cdot 2^{k+1}) has binary zeros in positions 0 through k, so ANDing it with either term leaves it unchanged.
   • The term (2^k) (a 1 at position k, 0s elsewhere) ANDed with (2^k -1) (1s in positions 0 through k-1, 0 at position k) gives 0.
   • All trailing bits (positions 0 through k-1) are 0 in x and 1 in x-1, so their AND is 0.

   The final result is (m \cdot 2^{k+1}), which is exactly x with its rightmost set bit removed.

For completeness, if x is 0 (all bits 0), x-1 in an n-bit system is an all-1s value. (0 & \text{all-1s} = 0), which fits the rule since 0 has no set bits to turn off.

内容的提问来源于stack exchange，提问作者user532913