Calculate the Number of 1's in Binary Representation

Introduction

Counting the number of 1's in the binary representation of integers is a common problem in computer science. In this article, we will explore an efficient solution to this problem using C#. The solution employs bitwise operations to count the 1's for each index from 0 to n, where n is the given integer.

Code Output. Before diving into the explanation, let's take a look at the output produced by the code snippet.

int n = 5;
Solution solution = new Solution();
int[] result = solution.CountBits(n);
Console.WriteLine(string.Join(", ", result));

Output: 0, 1, 1, 2, 1, 2

Explanation

The solution uses a straightforward approach to count the number of 1's for each index i, ranging from 0 to n.

Let's break down the code step by step.

1. Create an array answer of length n+1 to store the counts.

   var answer = new int[n + 1];
   answer[0] = 0;
   

2. Iterate from 1 to n and calculate the number of 1's for each index i.

   for (int i = 1; i <= n; i++) {
       var tn = i;
       while (tn > 0) {
           if ((tn & 1) > 0) {
               answer[i]++;
           }
           tn = tn >> 1;
       }
   }
   

3. The inner while loop extracts the least significant bit of the number tn using the bitwise AND operator (tn & 1). If the result is greater than 0, it means the bit is 1, and we increment the count for index i.
4. We then right-shift the number tn by 1 (tn = tn >> 1) to consider the next bit.
5. After the loop finishes, we have the counts of 1's for each index i in the answer array.

Complete code

public class Solution {
  public int[] CountBits(int n) {
    var answer = new int[n + 1];
    answer[0] = 0;

    // Algorithm
    // Count the number of 1's for each index i for a given integer n.
    for (int i = 1; i <= n; i++) {
      var tn = i;
      while (tn > 0) {
        if ((tn & 1) > 0) {
          answer[i]++;
        }
        tn = tn >> 1;
      }
    }
    return answer;
  }
}

Conclusion

In this article, we've presented an efficient solution to the "Counting Bits" problem using C#. By employing bitwise operations, we accurately determine the number of 1's in the binary representation of integers. This solution can be easily implemented in various scenarios that involve counting bits, such as optimizing algorithms, data compression, and more.

By understanding this solution and its underlying logic, you can confidently count the number of 1's in binary representations and leverage this knowledge in your own projects. Happy coding, and may your bits always be counted efficiently!