Getting the number of bits set in a large integer

Question

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.

• BЈовић: hint: modern computers are storing numbers as a power of 8, so you could use it

Answer 1

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.

Once you have your base-2^25 number then counting bits will, as you say, be quick and easy.

• Adrian Buzea: I do not understand how that helps. I get the number in base 10 so I'd still need to convert from base 10 to base 33554432 and that's basically what's taking a LOT of time.
• Martin Kochanski: Conversion by multiplication in base 33554432 is much, much, much faster than conversion by division in base 10.
• Adrian Buzea: I don't quite understand the process you're describing for converting by multiplication. Can you give an example ?
• Adrian Buzea: Nevermind, I get what you're saying now. I'll try it!
• Adrian Buzea: It worked and it's as you said, much much much faster :). Thank you!