C++ In Practice - Bit Manipulations

Bit Manipulation (C++11 Deep Dive)

Bit manipulation allows direct control over hardware registers and efficient data compression. In C++11, understanding specific integer types (<cstdint>) and Undefined Behavior (UB) regarding signed integers is critical for safety-critical systems.

C++11 Architecture & Types

The Header: <cstdint> (or <cinttypes>) Standard C++ int size is implementation-defined (usually 32-bit, but not guaranteed). For bitwise operations, always use fixed-width types to guarantee behavior across platforms.

int32_t, int64_t: Signed.
uint32_t, uint64_t: Unsigned.

Crucial Safety Rule: Prefer unsigned types for bitwise operations. In C++, shifting a negative signed integer right (>>) is implementation-defined (arithmetic vs. logical shift). Shifting a signed integer left (<<) into the sign bit is Undefined Behavior. Unsigned integers have well-defined wrapping behavior (modulo arithmetic).

1. Single Number (XOR Pattern)

Problem: All numbers appear twice, one appears once. Complexity: Time O(N) | Space O(1).

Under the Hood: The XOR operation (^) is a digital logic gate.

Commutative/Associative: Order doesn't matter. A ^ B ^ A is same as A ^ A ^ B.
Self-Inverse: A ^ A = 0.
Identity: 0 ^ B = B. Therefore, all pairs cancel out to 0, leaving the unique number.

#include <vector>
#include <numeric> // for std::accumulate (optional)

int singleNumber(const std::vector<int>& nums) {
    int result = 0;
    // Range-based for loop (C++11)
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

// STL Alternative (One-liner)
// Uses std::accumulate with a custom binary operation (std::bit_xor)
#include <functional>
int singleNumberSTL(const std::vector<int>& nums) {
    return std::accumulate(nums.begin(), nums.end(), 0, std::bit_xor<int>());
}

2. Hamming Weight (Number of 1 Bits)

Problem: Count set bits. Complexity: Time O(k) where k is the number of set bits (Brian Kernighan’s Algorithm).

Under the Hood:

Software Approach: n & (n - 1) removes the least significant bit (LSB).
Hardware Approach (Optimization): Modern CPUs (x86 SSE4.2+, ARM NEON) have a specific instruction POPCNT (Population Count). Compilers (GCC/Clang) expose this via __builtin_popcount(n). This reduces the operation to O(1) CPU cycles.

ASCII Visualization: n & (n-1)

State 1: n       = 101100  (Value: 44)
         n-1     = 101011  (Flips trailing 0s and lowest 1)
         n&(n-1) = 101000  (Lowest 1 removed)

State 2: n       = 101000
         n-1     = 100111
         n&(n-1) = 100000  (Next lowest 1 removed)

Implementation:

#include <cstdint>

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1); // Clear least significant bit
        count++;
    }
    return count;
}

// Compiler Intrinsic version (GCC/Clang) - O(1) instruction
int hammingWeightHardware(uint32_t n) {
    return __builtin_popcount(n); 
}

3. Counting Bits (Dynamic Programming)

Problem: Return array of bit counts for 0 to n. Complexity: Time O(N) | Space O(N).

Logic: A number x has the same bit pattern as x / 2 (x >> 1), plus the last bit (x & 1). dp[x] = dp[x >> 1] + (x & 1)

#include <vector>

std::vector<int> countBits(int n) {
    std::vector<int> dp(n + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= n; ++i) {
        // i >> 1 refers to a value already computed (smaller index)
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
}

4. Reverse Bits

Problem: Reverse bits of a 32-bit unsigned integer. Complexity: Time O(1) (Fixed 32 iterations).

Under the Hood: We maintain a result variable. We treat n as a queue of bits and result as a stack. We pop from n (read LSB, shift right) and push to result (shift left, write LSB).

#include <cstdint>

uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    // Iterate exactly 32 times for a 32-bit integer
    for (int i = 0; i < 32; ++i) {
        // 1. Shift result to make room
        result = result << 1;
        
        // 2. Add the LSB of n to result
        if (n & 1) {
            result = result | 1; // Set LSB of result to 1
        }
        
        // 3. Shift n to process next bit
        n = n >> 1;
    }
    return result;
}

5. Missing Number

Problem: Array [0...n] missing one number. Complexity: Time O(N) | Space O(1).

Logic: Index: 0 1 2 3 Value: 0 1 3 4 (Missing 2) XOR all indices: 0^1^2^3^4 (Includes n) XOR all values: 0^1^3^4 Result: 2 (Everything else cancels).

#include <vector>

int missingNumber(const std::vector<int>& nums) {
    int n = nums.size();
    int xorSum = n; // Initialize with n because loop only goes to n-1
    
    for (int i = 0; i < n; ++i) {
        // XOR the index and the value at that index
        xorSum ^= i ^ nums[i];
    }
    return xorSum;
}

6. Subsets (Power Set via Bitmask)

Problem: Generate all subsets. Complexity: Time O(N * 2^N) | Space O(N * 2^N).

System Limits: This approach works strictly for small N. Since a 32-bit integer can only enumerate 2^32 states, and memory is finite, this is practical only for N <= 20 roughly.