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 – BЈовић Sep 20 '16 at 14:14