CODEWITHSUNDEEP
c++bit-manipulation
user14270011
user14270011

Reputation:

Count total set-bits from 1 to n

I tried to solve this using loops. Can anyone tell me where I went wrong and what will be the output of it? I have tried using count set-bits concept for a given number.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int res=0;
    int n;
    cout<<"Enter the value of n";
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        while(i>0)
        {
            if((i & 1)==1)//checks whether the last bit is 1
            {
               res++; //res will count the set bits
            }
            i=i>>1;
        }

    }
    cout<<res;
}

Upvotes: 0

Views: 257

Answers (2)

A M
A M

Reputation: 15265

I will show some additional methods, how this can be done. There are some interesting approaches. Especially the last methods, which are taken from the book Hackers Delight. Unfortunately I cannot cite several pages from the book for the explanation. Please check the book.

But we will start with the standard "masking" approach. Easy to understand.

Next we will use a well known method, which is shown here on SO many times. It is about how to delete the right most set bit.

Method 3 is the "modern C++" solution using a std::bitset

Method 4 and 5 use a Divide and Conquer approach. They will produce some optimzed code for certain microcontrollers.

Please see the following example:

#include <iostream>
#include <bitset>

int main() {

    std::cout << "Enter an unsigned integer number: ";

    // Read number and check, if that worked
    if (unsigned int number{}; std::cin >> number) {

        // Method 1. Standard approach
        {
            unsigned int n{ number };
            unsigned int mask{ 1 };
            size_t count{};

            for (size_t i{}; i < sizeof(n) * 8; ++i) {
                if (n & mask) ++count;
                mask <<= 1;
            }
            std::cout << "\nMethod 1. Standard approach with masking. Set bits: " << count << '\n';
        }
        // Method 2. Improved version. Alwyas delete last set bit
        {
            unsigned int n{ number };
            size_t count{};
            while (n != 0) {
                ++count;
                // Deleting the rightmost set bit
                n = n & (n - 1);
            }
            std::cout << "\nMethod 2. Improved version. Alwyas delete last set bit. Set bits: " << count << '\n';
        }
        // Method 3. Using std::bitset
        {
            unsigned int n{ number };
            std::cout << "\nMethod 3. std::bitset. Set bits: " << std::bitset<32>(n).count() << '\n';
        }
        // Method 4. Loopless optimized Source: Hackers Delight
        {
            unsigned int n{ number };
            n = n - ((n >> 1) & 0x55555555);
            n = (n & 0x33333333) + ((n >> 2) & 0x33333333); 
            n = (n + (n >> 4)) & 0x0f0f0f0f;
            n = n + (n >> 8);
            n = n + (n >> 16);
            n = n & 0x0000003f;
            std::cout << "\nMethod 4. Hackers Delight 1. Set bits: " << n << '\n';
        }
        // Method 5. Loopless optimized Source: Hackers Delight 5
        {
            unsigned int x{ number };
            unsigned int n = (x >> 1) & 033333333333; // Octal constant
            x = x - n;
            n = (n >> 1) & 033333333333; // Octal constant
            x = x - n;
            x = ((x + (x >> 3)) & 030707070707) % 63;
            
            std::cout << "\nMethod 5. Hackers Delight 2. Set bits: " << x << '\n';
        }
    }
    else (std::cerr << "\n\nError: Invalid input\n");

    return 0;
}

Upvotes: 1

John Kugelman
John Kugelman

Reputation: 362087

General rule of thumb: Avoid modifying loop counter variables while iterating.

You're trying to loop i from 1 to n, but you modify i inside the loop and mess up successive iterations of the for loop. I advise making a copy of i and only modifying the copy.

Upvotes: 1

Related Questions