Ho bisogno di calcolare la base di log 2 di un numero in C ma non posso usare la libreria matematica. La risposta non deve essere esatta, solo per l'int più vicino. Ci ho pensato e so che potrei semplicemente usare un ciclo while e continuare a dividere il numero per 2 fino a quando non è < 2, e mantenere il conteggio delle iterazioni, ma è possibile usando operatori bit a bit?Come registrare il database di base 2 utilizzando operatori bit a bit?
Se si conta shifting come operatore bit a bit, questo è facile.
Sapete già come fare per divisione successive per 2.
x >> 1 è lo stesso x/2 per ogni intero senza segno in C.
Se avete bisogno di fare questo più veloce, si può fare un "divide e conquista": sposta, diciamo, 4 bit alla volta fino a raggiungere 0, quindi torna indietro e guarda gli ultimi 4 bit. Ciò significa al massimo 16 turni e 19 confronti invece di 63 di ciascuno. Non posso dire senza testare se sia effettivamente più veloce su una CPU moderna. E puoi fare un ulteriore passo avanti, prima fare gruppi di 16, poi 4, poi 1. Probabilmente non è utile qui, ma se avessi alcuni interi a 1024 bit, potrebbe valere la pena di prenderlo in considerazione.
Grazie, non mi rendevo conto di quanto fosse ovvio. L'avevo capito. – SKLAK
@SKLAK: per divertirti, prova a compilare il codice '/ 2' e' >> 1' con -O2 e vedi come si differenzia. Se uno è significativamente più veloce dell'altro, potresti ottenere lo stesso identico codice per entrambi. – abarnert
Saranno gli stessi per 'unsigned'. Per 'int', c'è un'operazione extra per aggiungere preventivamente il bit del segno, che assicura che il risultato giri verso lo zero piuttosto che l'infinito negativo. –
già risposto da abamert ma solo per essere più concreti in questo modo si sarebbe codificarlo:
Log2(x) = result
while (x >>= 1) result++;
contate [spostamento] (http://en.wikipedia.org/wiki/Bitwise_operation#Bit_shifts) come operatore bit a bit? Se è così, la risposta è abbastanza ovvia. In caso contrario, è più difficile. – abarnert
0_o Perché non puoi usare la libreria matematica? –
@JackManey: Presumibilmente si tratta di compiti a casa o equivalenti di autoapprendimento. Ma va bene; sembra che ci abbia messo un po 'di impegno (ha sempre una soluzione funzionante), e sta cercando suggerimenti per capire se c'è un altro modo per farlo, senza chiederci di fare i compiti per lui. – abarnert