ASP.NET Tutorial: How to Calculate the Number of 1's in Binary Representation?

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.

<span class="token class-name"><span class="token keyword keyword-int">int</span></span> n <span class="token operator">=</span> <span class="token number">5</span><span class="token punctuation">;</span>
<span class="token class-name">Solution</span> solution <span class="token operator">=</span> <span class="token keyword keyword-new">new</span> <span class="token constructor-invocation class-name">Solution</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token class-name"><span class="token keyword keyword-int">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span></span> result <span class="token operator">=</span> solution<span class="token punctuation">.</span><span class="token function">CountBits</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
Console<span class="token punctuation">.</span><span class="token function">WriteLine</span><span class="token punctuation">(</span><span class="token keyword keyword-string">string</span><span class="token punctuation">.</span><span class="token function">Join</span><span class="token punctuation">(</span><span class="token string">", "</span><span class="token punctuation">,</span> result<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

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.

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

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

<span class="token keyword keyword-for">for</span> <span class="token punctuation">(</span><span class="token class-name"><span class="token keyword keyword-int">int</span></span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token class-name"><span class="token keyword keyword-var">var</span></span> tn <span class="token operator">=</span> i<span class="token punctuation">;</span>
    <span class="token keyword keyword-while">while</span> <span class="token punctuation">(</span>tn <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword keyword-if">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>tn <span class="token operator">&amp;</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            answer<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">++</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        tn <span class="token operator">=</span> tn <span class="token operator">&gt;&gt;</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

for (int i = 1; i <= n; i++) {

var tn = i;

while (tn > 0) {

if ((tn & 1) > 0) {

answer[i]++;

}

tn = tn >> 1;

}

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.

We then right-shift the number tn by 1 (tn = tn >> 1) to consider the next bit.

After the loop finishes, we have the counts of 1’s for each index i in the answer array.

Complete code

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!

ASP.NET Hosting Recommendation

ASP.NET is a powerful platform for creating web applications and services. You must be comfortable with JavaScript, HTML, CSS, and C# before developing a web application in ASP.NET. On the market, there are thousands of web hosting companies providing ASP.NET Hosting. But, only very few web hosting companies could provide high quality ASP.NET hosting solution.

ASP.NET is the best development language in Windows platform, which is released by Microsoft and widely used to build all types of dynamic Web sites and XML Web services. With this article, we’re going to help you to find the best ASP.NET Hosting solution in Europe based on reliability, features, price, performance and technical support. After we reviewed about 30+ ASP.NET hosting providers in Europe, our Best ASP.NET Hosting Award in Europe goes to HostForLIFE.eu, one of the fastest growing private companies and one of the most reliable hosting providers in Europe.