2Brute2Best
🔥0
02

Bit counting / powers (Bit Manipulation Sub-pattern)

Questions about one number's bits: how many are set, whether exactly one is set, their reverse, or building a quotient from powers of two.

Signals in the problem statement
  • ›

    "number of 1 bits", "Hamming weight / distance"

  • ›

    "power of two / four"

  • ›

    "count bits for every number 0..n"

  • ›

    "reverse bits", "without multiplication or division"

What makes it different

Count / power → n & (n − 1). Counting for all of 0..n → DP: bits[i] = bits[i >> 1] + (i & 1). Reverse → exactly 32 shifts. Division → subtract the largest divisor · 2^k that fits, from the top bit down.

Questions

ordered from “learn the idea” to “recognise it without help”
  1. 1
    Number of 1 Bits
    Basic Anchor·LeetCode #191
    Easy
  2. 2
    Power of Two
    Basic Reinforcement·LeetCode #231
    Easy
  3. 3
    Counting Bits
    Slight Variation·LeetCode #338
    Easy
  4. 4
    Reverse Bits
    Medium·LeetCode #190
    Easy
  5. 5
    Divide Two Integers
    Pattern Transfer·LeetCode #29
    Medium

Template

bit-tricks-template.cpp
// n & (n - 1) removes the lowest 1-bit:  1100 -> 1000.
int countOnes(unsigned n) {
    int c = 0;
    while (n) { n &= n - 1; c++; }           // runs once per 1-bit
    return c;
}

// A power of two has exactly one 1-bit. Check n > 0 first (0, negatives, INT_MIN).
bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }

// x & -x keeps only the lowest 1-bit:  1100 -> 0100.
unsigned lowestBit(unsigned x) { return x & -x; }

// Read, set, clear, flip bit i (0 = rightmost). Use unsigned when i can be 31.
bool getBit(unsigned n, int i) { return (n >> i) & 1; }
unsigned setBit(unsigned n, int i) { return n | (1u << i); }
unsigned clearBit(unsigned n, int i) { return n & ~(1u << i); }
unsigned flipBit(unsigned n, int i) { return n ^ (1u << i); }

// Bits of every number 0..n: i without its last bit is i >> 1, already solved.
vector<int> countBitsUpTo(int n) {
    vector<int> bits(n + 1, 0);
    for (int i = 1; i <= n; i++) bits[i] = bits[i >> 1] + (i & 1);
    return bits;
}

// Reverse all 32 bits: exactly 32 steps, so leading zeros become trailing zeros.
uint32_t reverse32(uint32_t n) {
    uint32_t r = 0;
    for (int i = 0; i < 32; i++) { r = (r << 1) | (n & 1); n >>= 1; }
    return r;
}
Remember this · Bit Manipulation
Trigger
"Every element appears twice except…", power of two, counting set bits, subsets as bitmasks, O(1) space tricks.
Think
What happens to this problem if I look at each bit separately?
Key question
Which bit operation (XOR, AND, OR, shift) cancels or isolates what I need?
XOR cancellationRange bitwise properties