Ho un numero intero intero N < 10 ^ 2500. Ho bisogno di ottenere il numero di bit impostati nella sua rappresentazione binaria. Il numero è indicato nella base 10 in un file. Ecco come lo sto facendo adesso:
Ho creato una classe chiamata BigNumber che utilizza un array per memorizzare interi molto grandi.
- Sto analizzando il numero in un oggetto BigNumber in base 10.
- Sto convertendo detto numero in base
2^x(usando 25 per x ora, ma ciò che importa è che è una potenza di 2). Per la conversione uso ripetutamente il metodo standard di divisione della base fino a quando il quoziente è 0. - Poiché il numero di bit impostato in
a * 2^xè uguale al numero di bit impostato ina(possiamo scrivereacome somma dinpotenze di 2 e quando moltiplichiamo per una potenza di 2 otterremonfattori quindinbit) Ho solo bisogno di calcolare il numero di bit impostato in ogni cifra del mio numero usando Algoritmo SWAR per x < 32, e li riassumono.
Questo metodo funziona, ma è molto lento (richiede molto tempo per un numero di 2500 cifre), e presumo che sia dovuto alla mia implementazione dell'algoritmo di divisione o di cambio di base.
Qui è la mia intera classe BigNumber in C ++.
Mi sto avvicinando a questo nel modo giusto? E se sì, come posso farlo funzionare più velocemente?
This is for learning, not production code, so I'm not going to use already implemented libraries.