Bit manipulation¶

Bits help when each state component is binary. Name what each bit means before writing operators; compact code without a state model is difficult to verify.

Operation map¶

Need	Expression	Meaning
Test bit `b`	`mask & (1 << b)`	Is flag `b` present?
Add bit `b`	`mask \\| (1 << b)`	Preserve all flags and set `b`
Remove bit `b`	`mask & ~(1 << b)`	Preserve all flags except `b`
Toggle bit `b`	`mask ^ (1 << b)`	Flip exactly flag `b`
Lowest set bit	`mask & -mask`	Isolate the lowest active power of two
Clear lowest set bit	`mask & (mask - 1)`	Remove one active flag

Count set bits¶

PythonC++17C++11

def count_set_bits(value: int) -> int:
    """Count one-bits in a nonnegative integer."""
    if value < 0:
        raise ValueError("value must be nonnegative")
    count = 0
    while value:
        # Clearing the lowest set bit makes one unit of progress.
        value &= value - 1
        count += 1
    return count

inline int count_set_bits(long long value) {
  if (value < 0) {
    throw std::invalid_argument("value must be nonnegative");
  }
  unsigned long long remaining = static_cast<unsigned long long>(value);
  int count = 0;
  while (remaining != 0) {
    // Clearing the lowest set bit makes one unit of progress.
    remaining &= remaining - 1;
    ++count;
  }
  return count;
}

inline int count_set_bits(long long value) {
  if (value < 0) {
    throw std::invalid_argument("value must be nonnegative");
  }
  unsigned long long remaining = static_cast<unsigned long long>(value);
  int count = 0;
  while (remaining != 0) {
    // Clearing the lowest set bit makes one unit of progress.
    remaining &= remaining - 1;
    ++count;
  }
  return count;
}

The loop runs once per set bit: O(popcount(value)).

When a mask becomes DP state¶

flowchart LR
  accTitle: Building a subset dynamic-programming state
  accDescr: A mask records which small set of items is already used, a position records progress, and a transition adds one unused item. This is practical only when the number of bits is small.
  A["state(mask, position)"] --> B["choose unused bit b"]
  B --> C["state(mask OR 1&lt;&lt;b, position+1)"]

With k flags there are 2^k masks. Bit packing saves representation cost; it does not remove exponential state growth.

Practice ladder¶

Number of 1 Bits — clear the lowest bit.
Single Number — XOR cancellation.
Subsets — enumerate masks.
Can I Win — memoize a game by used-number mask.