Bit Manipulation and Bitmasking

Set, clear, toggle, test bit; isolate lowest set bit; count set bits; power-of-two test; XOR cancellation; parity; masks; and bit shifts.

Basics

Set, clear, toggle, test bit; isolate lowest set bit; count set bits; power-of-two test; XOR cancellation; parity; masks; and bit shifts. (Module 3.9 introduced the operators.)

Patterns

Single-number variants, subset enumeration, bitmask visited sets, bitwise trie, subset DP, SOS DP, and Gray code.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Gray codes list all n-bit values so that consecutive ones differ in exactly one bit (i ^ (i >> 1)). Iterating s = (s − 1) & mask visits every submask in decreasing order; over all masks this totals 3ⁿ steps.

#include <bits/stdc++.h>
using namespace std;

int kernighan(unsigned x) { int c = 0; while (x) { x &= x - 1; ++c; } return c; }   // one iteration per set bit

int main() {
    vector<int> a = {4, 1, 2, 1, 2};
    int single = 0;
    for (int x : a) single ^= x;                        // pairs cancel: x ^ x = 0
    cout << "single number in {4,1,2,1,2}: " << single << '\n';

    // two numbers appearing once, all others twice
    vector<int> b = {1, 2, 1, 3, 2, 5};
    int x = 0; for (int v : b) x ^= v;                  // x = p ^ q
    int bit = x & -x;                                   // a bit where p and q differ
    int p = 0, q = 0;
    for (int v : b) (v & bit ? p : q) ^= v;
    cout << "the two singles in {1,2,1,3,2,5}: " << min(p, q) << ' ' << max(p, q) << '\n';

    cout << "popcount of 0b1011011: Kernighan " << kernighan(0b1011011) << ", builtin " << __builtin_popcount(0b1011011) << '\n';

    // enumerate all submasks of a mask: s = (s - 1) & mask
    unsigned mask = 0b1011;
    cout << "submasks of 1011:";
    for (unsigned s = mask; ; s = (s - 1) & mask) { cout << ' ' << bitset<4>(s); if (s == 0) break; }
    cout << "\nGray code n=3:";
    for (unsigned i = 0; i < 8
…

single number in {4,1,2,1,2}: 4
the two singles in {1,2,1,3,2,5}: 3 5
popcount of 0b1011011: Kernighan 5, builtin 5
submasks of 1011: 1011 1010 1001 1000 0011 0010 0001 0000
Gray code n=3: 000 001 011 010 110 111 101 100
SOS sum for mask 101 = a[000]+a[001]+a[100]+a[101] = 1+2+16+32 = 51

Advanced topics

Brian Kernighan's algorithm, popcount, arithmetic bit tricks with proof, bitset acceleration, and undefined/implementation-defined behavior concerns in different languages.

x & (x − 1) clears the lowest set bit: subtracting 1 flips that bit and every zero below it.

x & −x isolates the lowest set bit (two's complement negation = invert and add 1).

std::bitset and word-level operations process 64 bits per instruction — the bitset subset-sum in Module 22 is a “divide by 64” speed-up.

Language differences: in Java >>> is the unsigned right shift; JavaScript bitwise operators work on 32-bit signed integers; Python integers are unbounded, so ~x is −x − 1 and masks must be applied explicitly.

Quiz

? Why does XOR-ing every element find the one that appears once?
+ x ^ x = 0 and XOR is associative and commutative, so pairs cancel. :: The run returned 4 for {4,1,2,1,2}.
- XOR finds the maximum. :: No.
- Because the array is sorted. :: It is not.
- It only works for powers of two. :: Works for any integers.

? How many iterations does Kernighan's popcount loop make?
+ One per set bit :: Each `x &= x − 1` clears the lowest set bit.
- One per bit position :: That is the naive loop.
- log₂ x :: Not exactly.
- Always 32 :: No.

? Which expressions isolate or clear the lowest set bit? (select all that apply)
+ `x & -x` isolates it :: Two's complement.
+ `x & (x - 1)` clears it :: Subtract-one flips the trailing zeros and that bit.
- `x | (x + 1)` isolates it :: That sets the lowest zero bit.
- `x >> 1` clears it :: It shifts every bit.