Count total set-bits from 1 to n

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.

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; }