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.
- I am parsing the number into a BigNumber object in base 10.
- 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.
- Because the number of bits set in
a * 2^xis equal to the number of bits set in
a(we can write
aas a sum of
npowers of 2 and when we multiply by a power of 2 we are going to get
nbits) 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.