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:

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.

Rust Solution

Rust's index-vs-value split drives the two casts here: Vec and slices index by usize, so num as usize converts the i32 argument up front, while count stores i32 values, forcing i as i32 % 2 to bring the usize loop index back down for the sum. The vec![0i32; n + 1] macro allocates and zero-fills in one step, and the 0i32 suffix pins the element type so the later arithmetic type-checks. The inclusive range 1..=n walks 1 through n without the off-by-one an exclusive .. would introduce, and the bare trailing count is the function's return value — no return keyword needed.

Go Solution

Because everything stays int — the num parameter, the slice elements, and the loop counter — Go needs none of Rust's index/value casts; count[i/2] and i%2 compose directly on the one type. make([]int, num+1) allocates the slice and zero-fills every element, so the base case is already correct without an explicit fill. The C-style for i := 1; i <= num; i++ and the short declaration count := are the idiomatic loop and binding, and return count hands back the []int slice by its header.