Eventuali duplicati:
Compute fast log base 2 ceilingScopri quante cifre binarie una particolare intero ha
Qual è il modo più veloce possibile per scoprire quante cifre binarie una particolare intero ha quando si viene convertito da decimale in binario in C/C++?
Es. 47 (10) = 101111 (2)
Così 47 ha 6 cifre rappresentate in binario.
La soluzione più veloce presentata a my favorite collection of bit twiddling hacks è Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup. Richiede 13 istruzioni per trovare il bit più alto in un numero.
uint32_t v; // find the log base 2 of 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
v |= v >> 1; // first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
Mentre penso che questo metodo di ORing sia bello (e come programmatore posso apprezzarlo artisticamente), non è ottimale. Stai facendo 10 operazioni del valore di OR e SHIFT, quindi esegui un MUL con un altro SHIFT, quindi esegui una LUT (Memory Lookup). Direi che è lento come i metodi Log2 che sono stati proposti. –
@LastCoder Che cosa stai pensando di fare log2 dietro le quinte? Questa implementazione ammette apertamente di aver bisogno di 13 istruzioni (non FP). – sblom
Se l'architettura di destinazione ha una cache veloce, il LUT non dovrebbe essere troppo costoso. –
Prova una logaritmo in base 2:
ceil(log2(n))
come circa 1? Zero cifre binarie? – ElKamina
L'OP chiede * il modo più veloce possibile *, e l'utilizzo di operazioni in virgola mobile come 'log2()' e 'ceil()' non è certamente il modo più veloce per questo tipo di problema. –
Se il numero intero è almeno 1, i bit necessari sarebbero:
floor(log2(x)) + 1
L'OP chiede * il modo più veloce possibile *, e l'uso di operazioni in virgola mobile come 'log2()' e 'ceil()' non è certamente il modo più veloce per questo tipo di problema. –
concordato. Non l'ho visto. Votare per chiudere in dupe. –
Per un modo divertente rapido di fare questo senza bisogno di richiamare le funzioni matematiche, controllare questo fuori:
for (digits = 0; val > 0; val >>= 1)
digits++;
Come bonus, questo dovrebbe cuocere fino a un carico di memoria e 2 registri a usa, per il whiz-bang extra.
Se si sta cercando il modo "più veloce" in termini di prestazioni, sarà necessario ricorrere a metodi specifici della piattaforma.
Alcune architetture hanno effettivamente un'istruzione che lo fa.
Su x86, si dispone dell'istruzione bsr.
In MSVC, è accessibile come:
inline int bitlength(unsigned long x){
if (x == 0)
return 0;
unsigned long index;
_BitScanReverse(&index,x);
return (int)(index + 1);
}
GCC ha la __builtin_clz() intrinsic - che fa qualcosa di simile.
Questa è la risposta che dovrebbe essere corretta (anche se è arrivata in un minuto prima del mio). L'opcode BSR è il metodo più veloce per x86, nel complesso le dichiarazioni IF branching sarebbero probabilmente le più veloci. –
Nota extra per completezza, il metodo di ramificazione IF che ho notato nel mio post è anche più veloce del metodo ORing (in un'altra risposta), ma più lento dell'istruzione BSR. snipt.org/xrom3 (312ms BSR, 406ms IFs, 671ms OR) Ho usato FlatAssembler per confrontare le funzioni. –
Il modo tradizionale
int count = 32;
for(int i = 1 << 31; i != 0; i >>= 1, count--)
if((number & i) != 0) return count;
È possibile ottenere ulteriori fantasia con l'ottimizzazione.
EDIT 2 Ecco il codice più veloce che potrei pensare senza l'utilizzo dell'opcode Bit Scan Reverse. È possibile utilizzare una LUT più grande (256 voci) e rimuovere l'ultima istruzione IF. Nel mio test questo è stato più veloce del ripetuto OR-SHIFT, quindi il metodo LUT descritto in un altro post.
int[] Log2_LUT = new int[16]{0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4};
int Log2 (number) {
int count = 0;
if((number & 0xFFFF0000) != 0) {
number >>= 16;
count += 16;
}
if((number & 0x0000FF00) != 0) {
number >>= 8;
count += 8
}
if((number & 0x000000F0) != 0) {
number >>= 4;
count += 4;
}
return count + Log2_LUT[number];
}
O se il vostro in architettura x86 o x86-64 bit è possibile utilizzare il codice operativo BSR (Bit Scan Reverse). Potete trovare il C++ intrinseca per esso http://msdn.microsoft.com/en-us/library/fbxyd7zd%28v=vs.80%29.aspx
Inoltre è in discussione è simile a questo What is the fastest way to calculate the number of bits needed to store a number
EDIT Perché le risposte log2 non sono ottimali ... Mentre le operazioni matematicamente corretto, virgola mobile complesse (seno, coseno, abbronzatura, log) sono le operazioni con prestazioni più lente sui computer moderni. Questo è aggravato dal fatto di dover convertire un intero in un float e di doverlo definire soffitto/pavimento.
Un modo è questo ...
unsigned int count_bits(unsigned int n)
{
unsigned int count = 0;
if (n <= 1)
return 1;
do
count++;
while(n >>= 1);
return count;
}
Se la velocità è più importante della portabilità, poi alcuni compilatori fornire una funzione di "contare gli zeri iniziali". Questo compila su una singola istruzione macchina su alcuni processori incluso il moderno x86 e ARM. Ad esempio, con GCC:
CHAR_BIT * sizeof x - __builtin_clz(x)
Che, fondamentalmente, vogliono [calcolare ceil (log2 (n))] (http://stackoverflow.com/questions/3272424/compute-fast-log-base-2-ceiling), che è già stato chiesto qui. –
_BitScanReverse (MSVC) o equivalente. Qualsiasi cosa che calcoli un logaritmo a virgola mobile viene immediatamente squalificata quando si richiede il modo più veloce. – harold
Il modo più veloce dipenderà dal processore, ma puoi trovare le soluzioni gcc e MS che utilizzeranno le istruzioni cpu qui: http://stackoverflow.com/questions/3272424/compute-fast-log-base-2-ceiling –