Counting Bits Solutions: Mastering Binary Representation Techniques

Comprehensive guide to solving counting bits problems in competitive programming, featuring efficient algorithms and bit manipulation techniques for the CSES problem set.

Counting Bits Solutions: Problems 1 to 3
1 Counting Set Bits
Problem 1
Count the number of 1-bits in the binary representation of a number n.
Definition:

Set bits: The number of 1s in the binary representation of a number

Solution approaches:
  1. Naive approach: Check each bit individually
  2. Brian Kernighan's algorithm: Efficient method to count set bits
  3. Built-in functions: Use language-specific functions
1
0
1
1
0
1
0
1
Step 1: Understand the problem

For number 181 (binary: 10110101), we need to count the number of 1s

Step 2: Implement Brian Kernighan's algorithm

n = n & (n-1) removes the rightmost set bit in each iteration

Step 3: Count iterations

Repeat until n becomes 0, counting each iteration

int countSetBits(int n) {
    int count = 0;
    while (n) {
        n = n & (n-1);  // Remove rightmost set bit
        count++;
    }
    return count;
}
For n = 181, result = 5
Final Answer:

The number of set bits in 181 is 5 (binary: 10110101 has 5 ones)

Key Properties:

• Time complexity: O(number of set bits) instead of O(log n)

• Bitwise AND: n & (n-1) removes the rightmost set bit

• Efficiency: Only iterates as many times as there are set bits

2 Creating All Subsets
Problem 2
Generate all subsets of a set with n elements using bit manipulation.
Definition:

Subset generation: Using binary representation to represent inclusion/exclusion of elements

1
0
1
1
0
Step 1: Understand the mapping

Each bit represents whether an element is included in the subset (1) or not (0)

Step 2: Iterate through all possibilities

From 0 to 2^n - 1, each number represents a unique subset

Step 3: Check each bit

For each number, check which bits are set to determine subset elements

void generateSubsets(vector& arr) {
    int n = arr.size();
    for (int i = 0; i < (1 << n); i++) {  // 2^n subsets
        vector subset;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {  // Check if j-th bit is set
                subset.push_back(arr[j]);
            }
        }
        print(subset);  // Print current subset
    }
}
For array [1,2,3]: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}
Final Answer:

Generated all 2^n subsets using bit manipulation, where each bit represents element inclusion

Key Properties:

• Binary representation: Each bit corresponds to an element in the set

• Range: Iterate from 0 to 2^n - 1 to cover all possible combinations

• Efficiency: O(n * 2^n) time complexity for generating all subsets

3 Sum of XOR Values
Problem 3
Given an array, compute the sum of XOR values of all pairs of elements.
Definition:

XOR sum: Sum of XOR values for all pairs (i,j) where i < j

1
0
1
0
1
1
Step 1: Analyze XOR properties

XOR is associative and commutative, and a ^ a = 0

Step 2: Process each bit position separately

For each bit position, count how many pairs contribute to the result

Step 3: Calculate contribution

For each bit position, contribution = (count of 1s) * (count of 0s) * (1 << bit_position)

long long xorSum(vector& arr) {
    long long result = 0;
    int n = arr.size();
    
    for (int bit = 0; bit < 32; bit++) {
        long long countOnes = 0;
        for (int num : arr) {
            if (num & (1 << bit)) {
                countOnes++;
            }
        }
        long long countZeros = n - countOnes;
        result += countOnes * countZeros * (1LL << bit);
    }
    return result;
}
For [1,2,3]: 1^2 + 1^3 + 2^3 = 3 + 2 + 1 = 6
Final Answer:

The sum of XOR values for all pairs in [1,2,3] is 6, computed efficiently using bit analysis

Key Properties:

• Bit-wise analysis: Process each bit position independently

• Contribution calculation: Each bit contributes based on count of 1s and 0s

• Efficiency: O(32n) instead of O(n²) brute force approach

Comprehensive Summary: Counting Bits Techniques
Complete Learning Guide

Definitions & Concepts

  • Binary representation: Numbers expressed in base-2 using only 0s and 1s
  • Set bits: Number of 1s in the binary representation of a number
  • Bit manipulation: Operations performed directly on binary representations
  • Bitmasking: Using binary numbers to represent sets or states

Core Rules & Principles

  • Bitwise operations: AND (&), OR (|), XOR (^), NOT (~), left shift (<<), right shift (>>)
  • Set bit identification: n & (1 << i) checks if the i-th bit is set
  • Set bit removal: n & (n-1) removes the rightmost set bit
  • Parity: XOR of all bits gives parity of the number of set bits

Step-by-Step Methods

  • Basic counting: Iterate through all bits and count 1s
  • Kernighan's algorithm: Use n = n & (n-1) to efficiently count set bits
  • Lookup table: Precompute results for smaller chunks
  • Divide and conquer: Process bits in groups

Examples (Simple → Advanced)

  • Simple: Count set bits in a single number: countSetBits(5) = 2 (binary: 101)
  • Intermediate: Generate all subsets using bit manipulation
  • Advanced: Calculate XOR sums of all pairs efficiently

Tips & Tricks

  • Power of 2 check: (n & (n-1)) == 0 indicates n is a power of 2
  • Rightmost set bit: n & (-n) isolates the rightmost set bit
  • Toggle all bits: ~n flips all bits (be careful with signed integers)
  • Fast multiplication/division: Left/right shifts for powers of 2

Common Pitfalls

  • Sign extension: Be careful with signed integers during bit operations
  • Overflow: Shifting beyond the integer width causes undefined behavior
  • Zero handling: Special cases when n = 0 in iterative algorithms
  • Integer limits: Consider using long long for large calculations

Memorization Aids

  • Kernighan's algorithm: n & (n-1) removes rightmost set bit
  • Subset generation: 1 << n creates 2^n combinations
  • Bit checking: n & (1 << i) tests if i-th bit is set
  • Set bit isolation: n & (-n) gets rightmost set bit
Advanced Bit Manipulation Techniques
4 Next Power of Two
Technique 4
Find the smallest power of two greater than or equal to n using bit manipulation.
Technique:

Round up to power of 2: Use bit manipulation to find the next power of two

1
0
0
0
0
Step 1: Handle edge case

If n is already a power of 2, return n

Step 2: Subtract 1 and set all bits

Subtract 1 to get n-1, then set all bits to the right of the highest set bit

Step 3: Add 1 to get power of 2

Add 1 to get the next power of two

int nextPowerOfTwo(int n) {
    if (n <= 1) return 1;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}
nextPowerOfTwo(10) = 16
Result:

Efficiently finds the next power of two using bitwise operations

5 Reverse Bits
Technique 5
Reverse the order of bits in a 32-bit integer efficiently.
Technique:

Bit reversal: Swap bits from opposite ends toward the center

1
0
1
0
1
0
1
0
Step 1: Swap adjacent bits

Exchange pairs of adjacent bits

Step 2: Swap adjacent 2-bit groups

Exchange pairs of 2-bit groups

Step 3: Continue with larger groups

Repeat with 4-bit, 8-bit, and 16-bit groups

uint32_t reverseBits(uint32_t n) {
    n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
    n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
    n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
    n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
    n = (n >> 16) | (n << 16);
    return n;
}
Reverses all 32 bits in O(1) time
Result:

Efficiently reverses all bits using divide-and-conquer approach

Common Problem Patterns and Solutions
BitOps + Math = Efficiency
Programming Equation
Common Patterns:

Subset enumeration: Using 0 to 2^n - 1 to represent all subsets

Parity checks: Using XOR to determine odd/even occurrences

Single element problems: Finding unique elements using XOR properties

Algorithmic Approaches:
  1. Brute force: Try all possibilities using bitmasks
  2. Optimized counting: Process each bit position independently
  3. Mathematical properties: Use XOR and AND properties
  4. Dynamic programming: With bitmasks for state representation
Tip 1: Always consider if a problem can be solved using bit manipulation.
Tip 2: Look for patterns in binary representations of inputs.
Tip 3: Use built-in functions like __builtin_popcount() when available.
Tip 4: Test with small examples to understand the bit patterns.
Performance gains: Bit operations are typically faster than arithmetic.
Memory efficiency: Bitmasks can compress state information significantly.
Best Practices:

• Use unsigned integers when performing bit operations

• Be careful with operator precedence in complex expressions

• Document bit manipulation code thoroughly

• Consider edge cases like 0 and negative numbers

Questions & Answers

Question: What is Brian Kernighan's algorithm and why is it more efficient than naive counting?

Answer: Brian Kernighan's algorithm uses the property that n & (n-1) removes the rightmost set bit from n.

In the naive approach, we check all bits (O(log n)), but in Kernighan's algorithm, we only iterate as many times as there are set bits (O(number of set bits)). For sparse numbers with few set bits, this is significantly faster.

Example: For n = 12 (binary: 1100), the algorithm only runs 2 iterations (for the 2 set bits) instead of 4 (log₂12 ≈ 4).

Question: How do I know when to use bit manipulation instead of regular arithmetic?

Answer: Consider bit manipulation when you notice these patterns:

  • Problems involving powers of 2 or binary representations
  • Need to track inclusion/exclusion (subset problems)
  • Operations like finding unique elements or pairs
  • Parity checks or toggling states
  • Problems where you need to optimize O(n²) to O(n) or O(log n)

Bit operations are typically faster and can lead to elegant solutions for these types of problems.

Question: Can you explain how (n & (n-1)) removes the rightmost set bit?

Answer: When you subtract 1 from a number, it flips all bits starting from the rightmost set bit:

If n = 12 (binary: 1100), then n-1 = 11 (binary: 1011)

n & (n-1) = 1100 & 1011 = 1000

The rightmost set bit (at position 2) and all trailing zeros are cleared. This works because subtracting 1 borrows from the rightmost set bit, turning it to 0 and setting all trailing zeros to 1s. The AND operation then clears those bits.