How x & -x Extracts the Lowest Set Bit in Binary

In low-level bitwise manipulation, the expression x & -x is an efficient technique used to isolate the least significant set bit (the rightmost bit equal to 1) of an integer. This operation works because modern computers represent negative integers using the Two’s Complement system. By inverting the bits and adding one, Two’s Complement preserves the lowest set bit and its trailing zeros while inverting every bit to its left, allowing the bitwise AND operation (&) to cancel out all other bits except the lowest 1.

Understanding the Structure of an Integer

Any non-zero integer \(x\) in binary can be conceptually divided into three distinct segments from left to right: 1. Prefix: The arbitrary pattern of bits to the left of the lowest set bit. 2. Lowest Set Bit: The rightmost 1. 3. Suffix: Zero or more trailing 0s to the right of the lowest set bit.

Represented abstractly: \[\text{x} = \text{[Prefix]} \; 1 \; [00\dots0]\]

Step 1: Generating -x with Two’s Complement

To negate a number in Two’s Complement arithmetic, you invert all bits (apply the bitwise NOT, ~) and then add 1:

\[\text{-x} = \sim\text{x} + 1\]

  1. Invert the bits (\(\sim\text{x}\)):

    • The [Prefix] becomes [~Prefix].
    • The lowest set bit 1 becomes 0.
    • The trailing [00...0] become trailing [11...1].

    \[\sim\text{x} = [\sim\text{Prefix}] \; 0 \; [11\dots1]\]

  2. Add 1 (\(\sim\text{x} + 1\)):

    • Adding 1 to the trailing [11...1] flips them all back to [00...0].
    • This addition generates a carry bit that propagates upward until it reaches the 0 (the former position of the lowest set bit), turning it into a 1.
    • The carry stops here, leaving [~Prefix] completely unchanged.

    \[\text{-x} = [\sim\text{Prefix}] \; 1 \; [00\dots0]\]

Step 2: Applying the Bitwise AND (x & -x)

When you perform the bitwise AND operation between \(x\) and \(-x\), each segment interacts as follows:

Combining these segments yields: \[\text{x \& -x} = [00\dots0] \; 1 \; [00\dots0]\]

Every bit in the number is cleared to 0 except for the original lowest set bit.

Step-by-Step Example

Consider the integer \(x = 12\) in an 8-bit binary representation:

  1. Binary of \(x\) (12): 00001100 (The lowest set bit is at position 2, representing \(2^2 = 4\)).

  2. Bitwise NOT (\(\sim x\)): 11110011

  3. Two’s Complement (\(-x = \sim x + 1\)): 11110100 (which is -12 in decimal).

  4. Bitwise AND (\(x \ \& \ -x\)):

      00001100  ( 12)
& 11110100  (-12)
----------
  00000100  (  4)

The result is 00000100 (decimal 4), which is the isolated lowest set bit of 12. If \(x = 0\), the expression safely evaluates to 0 because 0 & 0 produces 0.