Counting Bits: A Bit Manipulation Challenge

The "Counting Bits" problem is a classic bit manipulation challenge, often encountered in coding interviews. It requires counting the number of 1s (set bits) in the binary representation of each number from 0 up to a given integer.

Problem Statement

Given a non-negative integer num, the objective is to return an array count such that count[i] represents the number of 1s in the binary representation of i, for all 0 <= i <= num.

Dynamic Programming Solution

Here's a JavaScript function that employs dynamic programming to solve this problem:

function countBits(num) {
  const count = new Array(num + 1).fill(0);

  for (let i = 1; i <= num; i++) {
    count[i] = count[Math.floor(i / 2)] + (i % 2);
  }

  return count;
}

Breaking Down the Solution

• Initialize Array: An array count of size num + 1 is initialized with zeros. This array is crucial for storing the number of set bits (1s) for each number from 0 to num.

• Iterative Computation: A loop is executed, iterating through numbers from 1 to num. In each iteration, the number of set bits for the current number i is calculated. This is done by leveraging the results computed in previous iterations.

• Using Previous Results: The expression count[Math.floor(i / 2)] + (i % 2) effectively calculates the number of set bits in i. The idea is that the number of set bits in i is equal to the number of set bits in i / 2 (which is the same number right-shifted by one bit) plus an additional bit if i is odd. The extra bit comes from the fact that odd numbers have their least significant bit set to 1.

• Return the Result: After completing the iterations, the array count contains the number of set bits for each number in the range from 0 to num. This array is then returned as the final result.

Conclusion

The "Counting Bits" problem showcases the elegance of dynamic programming when applied to bit manipulation. It demonstrates how complex problems can be simplified into smaller subproblems. By iteratively building up the solution and utilizing previously computed results, the algorithm efficiently counts set bits across a range of numbers, highlighting the synergistic power of dynamic programming and bitwise operations in algorithmic problem-solving.