Twos-Complement Arithmetic, Bitmasks, Brian Kernighan's Trick & XOR

Two's Complement Ring Algebra & Lowest-Bit Identities

In a $w$-bit two's-complement register, a bit vector $b_{w-1} b_{w-2} \dots b_1 b_0$ represents the signed integer value:

$$x = -b_{w-1} 2^{w-1} + \sum_{i=0}^{w-2} b_i 2^i$$

Why did two's complement universally triumph over sign-magnitude and ones' complement? Because addition, subtraction, and multiplication use the exact same ALU circuitry for both signed and unsigned integers modulo $2^w$, and zero has a unique representation. Suppose a non-zero integer $x$ has its lowest set bit ($1$) at index $k$, so its binary representation splits into an arbitrary prefix $P$, bit $k$ equal to $1$, and $k$ trailing zeros: $x = [P \;\vert\; 1 \;\vert\; 00\dots0_k]$. Observe what happens under subtraction of $1$ and under negation ($\sim x + 1$):

• Subtracting 1 ($x - 1$): Borrowing from bit $k$ flips bit $k$ to $0$ and turns all $k$ trailing zeros into $1$s, leaving prefix $P$ untouched: $x - 1 = [P \;\vert\; 0 \;\vert\; 11\dots1_k]$.
• Brian Kernighan's Clear-Lowest-Set-Bit ($x \mathrel{\&} (x - 1)$): ANDing $x$ with $x - 1$ preserves prefix $P$ and zeroes out bit $k$ and everything below it: $x \mathrel{\&} (x - 1) = [P \;\vert\; 0 \;\vert\; 00\dots0_k]$. This clears the lowest set bit in $O(1)$ time, and equals $0$ for $x > 0$ if and only if $x$ is a power of two!
• Isolating the Lowest Set Bit ($x \mathrel{\&} -x$): Bitwise NOT gives $\sim x = [\sim P \;\vert\; 0 \;\vert\; 11\dots1_k]$. Adding $1$ ripples a carry through the $k$ trailing ones and sets bit $k$: $-x = \sim x + 1 = [\sim P \;\vert\; 1 \;\vert\; 00\dots0_k]$. Therefore, $x \mathrel{\&} -x = [00\dots0 \;\vert\; 1 \;\vert\; 00\dots0_k] = 2^k$, isolating the lowest set bit (the fundamental primitive of Fenwick Trees).

Essential Bit Manipulation Primitives & x86 BMI1/BMI2 Instructions

Visualizing Two's-Complement Bit Isolation & $O(3^n)$ Submask Jumping

Why Enumerating All Submasks of All Masks Takes $O(3^n)$ Instead of $O(4^n)$

Production Implementation: Single Number III, Gosper's Hack & $O(3^n)$ Submask DP

#include <bit>
#include <cstdint>
#include <utility>
#include <vector>

// Partition an array where two elements appear once and all others appear twice
std::pair<int, int> single_number_two_uniques(const std::vector<int>& nums) noexcept {
  std::uint32_t xor_all = 0;
  for (int x : nums) {
    xor_all ^= static_cast<std::uint32_t>(x);
  }
  // Isolate lowest differing bit using unsigned two's complement negation (safe for INT_MIN!)
  const std::uint32_t diff_bit = xor_all & (0u - xor_all);

  std::uint32_t group_a = 0, group_b = 0;
  for (int x : nums) {
    const auto ux = static_cast<std::uint32_t>(x);
    if ((ux & diff_bit) != 0) {
      group_a ^= ux;
    } else {
      group_b ^= ux;
    }
  }
  return {static_cast<int>(group_a), static_cast<int>(group_b)};
}

// Gosper's Hack: Compute next lexicographical bitmask with the exact same popcount
constexpr std::uint64_t next_combination_mask(std::uint64_t x) noexcept {
  const std::uint64_t c = x & (0ULL - x); // lowest set bit
  const std::uint64_t r = x + c;          // ripple carry through lowest block of 1s
  return (((r ^ x) >> 2) / c) | r;        // shift remaining 1s to the bottom
}

// Enumerate all submasks of all n-bit masks in exactly O(3^n) steps
void enumerate_all_submasks(int n) noexcept {
  const std::uint32_t total = 1u << n;
  for (std::uint32_t mask = 0; mask < total; ++mask) {
    for (std::uint32_t sub = mask; sub > 0; sub = (sub - 1) & mask) {
      // Process non-empty submask sub of mask
    }
    // Process sub == 0 here if empty submask is needed
  }
}