# Getting the number of bits set in a large integer

I have a large integer N < 10^2500. I need to get the number of bits set in its binary representation. The number is given in base 10 in a file. Here's how I'm doing it right now :

I made a class called BigNumber which uses an array to store very big integers.

1. I am parsing the number into a BigNumber object in base 10.
2. I am converting said number into base `2^x` (using 25 for x now, but what matters is that it is a power of 2). For conversion I use the standard method of division by the base repeatedly until the quotient is 0.
3. Because the number of bits set in `a * 2^x` is equal to the number of bits set in `a` (we can write `a` as a sum of `n` powers of 2 and when we multiply by a power of 2 we are going to get `n` factors so `n` bits) I just need to calculate the number of bits set in every digit of my number using the SWAR algorithm for x < 32, and them sum them up.

This method works, but it is very slow(takes a very long time for a 2500 digit number), and I am assuming it's because of my implementation of division or base change algorithm.

Here's my whole BigNumber class in C++.

Am I approaching this the right way ? And if so, how can I make it run faster ?

This is for learning, not production code, so I'm not going to use already implemented libraries.

• hint: modern computers are storing numbers as a power of 8, so you could use it Sep 20, 2016 at 14:14

You have rather tied your hands by storing your `BigNumber` in base 10, but I can see the practicalities of doing that, both for input and output and for general debugging.
Division is always slower than you'd expect, so you should create a new `BigNumber33554432` class which uses base 2^25 instead of base 10. You only need it to be able to add numbers between 1 and 9 into a BigNumber and to multiply a BigNumber by 10, so it will be really easy to write and fast to execute. Then you can convert your base-10 numbers to base 2^25 by reading the digits from left to right. At each step, multiply your current result by 10 and add the new digit.