Day 55: Counting Bits #

Welcome to Day 55 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the problem of Counting Bits, which involves efficiently counting the number of set bits (1s) in binary representations of numbers.

What is Bit Counting? #

Bit counting, also known as population count or popcount, is the process of counting the number of 1s in the binary representation of a number. This operation is fundamental in many areas of computer science and has applications in cryptography, error correction, and more.

Approaches to Counting Bits #

We’ll explore several approaches to count bits, ranging from simple to more optimized algorithms:

1. Naive Approach #

This approach simply checks each bit of the number:

1def count_bits_naive(n):
2    count = 0
3    while n:
4        count += n & 1
5        n >>= 1
6    return count
7
8# Example usage
9print(count_bits_naive(13))  # Output: 3 (13 is 1101 in binary)

Time Complexity: O(log n), where n is the number.

2. Brian Kernighan’s Algorithm #

This algorithm uses the fact that subtracting 1 from a number flips all bits after the rightmost set bit:

1def count_bits_kernighan(n):
2    count = 0
3    while n:
4        n &= (n - 1)
5        count += 1
6    return count
7
8# Example usage
9print(count_bits_kernighan(13))  # Output: 3

Time Complexity: O(number of set bits)

3. Lookup Table #

We can use a pre-computed lookup table for small numbers and combine results for larger numbers:

 1def initialize_lookup_table():
 2    table = [0] * 256
 3    for i in range(256):
 4        table[i] = (i & 1) + table[i // 2]
 5    return table
 6
 7LOOKUP_TABLE = initialize_lookup_table()
 8
 9def count_bits_lookup(n):
10    return (LOOKUP_TABLE[n & 0xff] +
11            LOOKUP_TABLE[(n >> 8) & 0xff] +
12            LOOKUP_TABLE[(n >> 16) & 0xff] +
13            LOOKUP_TABLE[(n >> 24) & 0xff])
14
15# Example usage
16print(count_bits_lookup(13))  # Output: 3

Time Complexity: O(1) for 32-bit integers

4. Built-in Function #

Python provides a built-in function to count bits:

1def count_bits_builtin(n):
2    return bin(n).count('1')
3
4# Example usage
5print(count_bits_builtin(13))  # Output: 3

5. Dynamic Programming Approach #

This approach builds on the fact that the number of set bits in n is equal to the number of set bits in n//2 plus 1 if n is odd:

 1def count_bits_dp(num):
 2    if num == 0:
 3        return [0]
 4    dp = [0] * (num + 1)
 5    for i in range(1, num + 1):
 6        dp[i] = dp[i >> 1] + (i & 1)
 7    return dp
 8
 9# Example usage
10print(count_bits_dp(5))  # Output: [0, 1, 1, 2, 1, 2]

Time Complexity: O(n) Space Complexity: O(n)

Applications of Bit Counting #

1. Cryptography: Used in various cryptographic algorithms.
2. Error Detection and Correction: Hamming weight (number of set bits) is used in error-correcting codes.
3. Compiler Optimizations: Used in certain low-level optimizations.
4. Network Protocols: Used in various network protocols for packet processing.

Variations and Related Problems #

1. Counting Bits in a Range: Count the total number of set bits for all numbers in a given range.
2. Next Number with Same Number of 1 Bits: Find the next higher number with the same number of set bits.
3. Missing Number in Array: Find the missing number in an array using XOR and bit counting.

Exercise #

1. Implement a function to count the total number of set bits for all numbers from 1 to n.
2. Write a function to find the number of flips required to convert number A to number B (i.e., count the differing bits).
3. Implement a function to determine if a number is a power of 4 using bit manipulation techniques.

Summary #

Today, we explored various approaches to the Counting Bits problem, from simple iterations to more optimized algorithms using bit manipulation techniques. We discussed the time complexities of these approaches and looked at some applications and variations of the problem.

Understanding bit counting algorithms is crucial for optimizing certain types of computations and is widely used in various areas of computer science, from low-level systems programming to cryptography.

Tomorrow, we’ll dive into String Algorithms, starting with the Knuth-Morris-Pratt (KMP) Algorithm for pattern matching. Stay tuned!