Qual è il modo più veloce / più efficace per trovare il bit più elevato (msb) in un intero in C?

Se ho un intero n, e voglio conoscere la posizione del bit più significativo (cioè, se il bit meno significativo è a destra, voglio sapere la posizione del bit più a sinistra che è un 1), qual è il metodo più rapido / efficace per scoprirlo?

So che POSIX supporta un metodo ffs() in strings.h per trovare il primo bit impostato, ma non sembra essere un metodo fls() corrispondente.

C’è un modo davvero ovvio di fare ciò che mi manca?

Che dire nei casi in cui non è ansible utilizzare le funzioni POSIX per la portabilità?

Modifica: Che dire di una soluzione che funziona su entrambe le architetture a 32 e 64 bit (molti degli elenchi di codice sembrano funzionare solo su 32 bit).

GCC ha :

  - Funzione built-in: int __builtin_clz (unsigned int x)
      Restituisce il numero di 0 bit iniziali in X, iniziando al massimo
      posizione bit significativa.  Se X è 0, il risultato non è definito.

  - Funzione built-in: int __builtin_clzl (non firmato lungo)
      Simile a `__builtin_clz ', tranne che il tipo di argomento è` unsigned
      lungo'.

  - Funzione built-in: int __builtin_clzll (non firmato lungo)
      Simile a `__builtin_clz ', tranne che il tipo di argomento è` unsigned
      lungo lungo'. 

Mi aspetterei che venissero tradotti in qualcosa di abbastanza efficiente per la tua attuale piattaforma, sia che si tratti di uno di quei fantasiosi algoritmi di bit-beat, o di una singola istruzione.

Supponendo che tu sia su x86 e giochi per un po ‘di assemblatore in linea, Intel fornisce un’istruzione BSR (“bit scan reverse”). È veloce su alcuni x86 (microcodificati su altri). Dal manuale:

Cerca l’operando sorgente per il bit di impostazione più significativo (1 bit). Se viene trovato un 1 bit più significativo, il suo indice di bit viene memorizzato nell’operando di destinazione. L’operando sorgente può essere un registro o una posizione di memoria; l’operando di destinazione è un registro. L’indice di bit è un offset senza segno dal bit 0 dell’operando di origine. Se l’operando dell’origine del contenuto è 0, il contenuto dell’operando di destinazione non è definito.

(Se sei su PowerPC c’è cntlz simile cntlz (“count leading cntlz “).)

Codice di esempio per gcc:

 #include  int main (int,char**) { int n=1; for (;;++n) { int msb; asm("bsrl %1,%0" : "=r"(msb) : "r"(n)); std::cout < < n << " : " << msb << std::endl; } return 0; } 

Vedi anche questo tutorial sull'assemblatore in linea , che mostra (sezione 9.4) che è considerevolmente più veloce del codice di looping.

Poiché 2 ^ N è un numero intero con solo l’ennesimo bit impostato (1 < < N), la ricerca della posizione (N) del bit più alto è la base del registro intero 2 di tale intero.

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

 unsigned int v; unsigned r = 0; while (v >>= 1) { r++; } 

Questo algoritmo “ovvio” potrebbe non essere trasparente per tutti, ma quando ci si rende conto che il codice si sposta di un bit ripetutamente fino a quando il bit più a sinistra non viene spostato (si noti che C considera qualsiasi valore diverso da zero come vero) e restituisce il numero di turni, ha perfettamente senso. Significa anche che funziona anche quando è impostato più di un bit – il risultato è sempre per il bit più significativo.

Se scorri verso il basso su quella pagina, ci sono variazioni più veloci e più complesse. Tuttavia, se si sa che si tratta di numeri con molti zeri iniziali, l’approccio ingenuo può fornire una velocità accettabile, poiché lo spostamento dei bit è piuttosto rapido in C, e il semplice algoritmo non richiede l’indicizzazione di un array.

NOTA: quando si usano valori a 64 bit, sii estremamente cauto nell’usare algoritmi estremamente intelligenti; molti di loro funzionano correttamente solo per valori a 32 bit.

Questo dovrebbe essere veloce:

 int msb(unsigned int v) { static const int pos[32] = {0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9}; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; v = (v >> 1) + 1; return pos[(v * 0x077CB531UL) >> 27]; } 

Questo è un po ‘come trovare un tipo di registro intero. Ci sono trucchetti che mi danno fastidio, ma ho creato il mio strumento per questo. L’objective, naturalmente, è per la velocità.

La mia realizzazione è che la CPU ha già un rilevatore di bit automatico, usato per convertire la conversione in numeri interi! Quindi usalo.

 double ff=(double)(v|1); return ((*(1+(uint32_t *)&ff))>>20)-1023; // assumes x86 endianness 

Questa versione converte il valore in double, quindi legge l’esponente, che indica dove si trovava il bit. Lo spostamento e la sottrazione di fantasia sono l’estrazione delle parti corrette dal valore IEEE.

È leggermente più veloce usare i float, ma un float può solo darti le prime posizioni a 24 bit a causa della sua precisione più piccola.


Per farlo in modo sicuro, senza un comportamento indefinito in C ++ o C, usa memcpy invece del cast del puntatore per il tipo puning. I compilatori sanno come farlo in modo efficiente.

 // static_assert(sizeof(double) == 2 * sizeof(uint32_t), "double isn't 8-byte IEEE binary64"); // and also static_assert something about FLT_ENDIAN? double ff=(double)(v|1); uint32_t tmp; memcpy(&tmp, ((const char*)&ff)+sizeof(uint32_t), sizeof(uint32_t)); return (tmp>>20)-1023; 

O in C99 e versioni successive, usa union {double d; uint32_t u[2];}; union {double d; uint32_t u[2];}; . Nota che in C ++ la punteggiatura dei tipi di unione è supportata solo su alcuni compilatori come estensione, non in ISO C ++.


Questo di solito sarà più lento di un intrinseco specifico della piattaforma per un’istruzione di conteggio degli zeri iniziali, ma l’ISO C portatile non ha tale funzione. Ad alcune CPU manca anche un’istruzione di conteggio a zero zero, ma alcune di queste possono convertire in modo efficiente interi in double . La punteggiatura di tipo di un modello di bit FP su intero può essere lenta, tuttavia (ad esempio su PowerPC richiede uno store / ricarica e solitamente provoca uno stallo di load-hit-store).

Questo algoritmo potrebbe essere utile per le implementazioni SIMD, perché un numero inferiore di CPU ha un lzcnt SIMD. x86 ha ottenuto solo un’istruzione simile con AVX512CD

Kaz Kylheku qui

Ho messo a confronto due approcci per questo numero di bit over 63 (il tipo long lungo su gcc x86_64), stando lontano dal bit del segno.

(Mi capita di aver bisogno di questo “trova il più alto” per qualcosa, vedi).

Ho implementato la ricerca binaria basata sui dati (strettamente basata su una delle risposte precedenti). Ho anche implementato manualmente un albero delle decisioni completamente srotolato, che è solo codice con operandi immediati. Niente loop, niente tavoli.

L’albero delle decisioni (highest_bit_unrolled) è benchmarking del 69% più veloce, ad eccezione del caso n = 0 per il quale la ricerca binaria ha un test esplicito.

Il test speciale di ricerca binaria per il caso 0 è solo il 48% più veloce dell’albero decisionale, che non ha un test speciale.

Compilatore, macchina: (GCC 4.5.2, -O3, x86-64, 2867 Mhz Intel Core i5).

 int highest_bit_unrolled(long long n) { if (n & 0x7FFFFFFF00000000) { if (n & 0x7FFF000000000000) { if (n & 0x7F00000000000000) { if (n & 0x7000000000000000) { if (n & 0x4000000000000000) return 63; else return (n & 0x2000000000000000) ? 62 : 61; } else { if (n & 0x0C00000000000000) return (n & 0x0800000000000000) ? 60 : 59; else return (n & 0x0200000000000000) ? 58 : 57; } } else { if (n & 0x00F0000000000000) { if (n & 0x00C0000000000000) return (n & 0x0080000000000000) ? 56 : 55; else return (n & 0x0020000000000000) ? 54 : 53; } else { if (n & 0x000C000000000000) return (n & 0x0008000000000000) ? 52 : 51; else return (n & 0x0002000000000000) ? 50 : 49; } } } else { if (n & 0x0000FF0000000000) { if (n & 0x0000F00000000000) { if (n & 0x0000C00000000000) return (n & 0x0000800000000000) ? 48 : 47; else return (n & 0x0000200000000000) ? 46 : 45; } else { if (n & 0x00000C0000000000) return (n & 0x0000080000000000) ? 44 : 43; else return (n & 0x0000020000000000) ? 42 : 41; } } else { if (n & 0x000000F000000000) { if (n & 0x000000C000000000) return (n & 0x0000008000000000) ? 40 : 39; else return (n & 0x0000002000000000) ? 38 : 37; } else { if (n & 0x0000000C00000000) return (n & 0x0000000800000000) ? 36 : 35; else return (n & 0x0000000200000000) ? 34 : 33; } } } } else { if (n & 0x00000000FFFF0000) { if (n & 0x00000000FF000000) { if (n & 0x00000000F0000000) { if (n & 0x00000000C0000000) return (n & 0x0000000080000000) ? 32 : 31; else return (n & 0x0000000020000000) ? 30 : 29; } else { if (n & 0x000000000C000000) return (n & 0x0000000008000000) ? 28 : 27; else return (n & 0x0000000002000000) ? 26 : 25; } } else { if (n & 0x0000000000F00000) { if (n & 0x0000000000C00000) return (n & 0x0000000000800000) ? 24 : 23; else return (n & 0x0000000000200000) ? 22 : 21; } else { if (n & 0x00000000000C0000) return (n & 0x0000000000080000) ? 20 : 19; else return (n & 0x0000000000020000) ? 18 : 17; } } } else { if (n & 0x000000000000FF00) { if (n & 0x000000000000F000) { if (n & 0x000000000000C000) return (n & 0x0000000000008000) ? 16 : 15; else return (n & 0x0000000000002000) ? 14 : 13; } else { if (n & 0x0000000000000C00) return (n & 0x0000000000000800) ? 12 : 11; else return (n & 0x0000000000000200) ? 10 : 9; } } else { if (n & 0x00000000000000F0) { if (n & 0x00000000000000C0) return (n & 0x0000000000000080) ? 8 : 7; else return (n & 0x0000000000000020) ? 6 : 5; } else { if (n & 0x000000000000000C) return (n & 0x0000000000000008) ? 4 : 3; else return (n & 0x0000000000000002) ? 2 : (n ? 1 : 0); } } } } } int highest_bit(long long n) { const long long mask[] = { 0x000000007FFFFFFF, 0x000000000000FFFF, 0x00000000000000FF, 0x000000000000000F, 0x0000000000000003, 0x0000000000000001 }; int hi = 64; int lo = 0; int i = 0; if (n == 0) return 0; for (i = 0; i < sizeof mask / sizeof mask[0]; i++) { int mi = lo + (hi - lo) / 2; if ((n >> mi) != 0) lo = mi; else if ((n & (mask[i] < < lo)) != 0) hi = mi; } return lo + 1; } 

Programma di test rapido e sporco:

 #include  #include  

Usando solo -O2, la differenza diventa maggiore. L'albero decisionale è quasi quattro volte più veloce.

Ho anche confrontato il codice del bit shifting ingenuo:

 int highest_bit_shift(long long n) { int i = 0; for (; n; n >>= 1, i++) ; /* empty */ return i; } 

Questo è veloce solo per i piccoli numeri, come ci si aspetterebbe. Nel determinare che il bit più alto è 1 per n == 1, ha benchmarkato più dell'80% più velocemente. Tuttavia, la metà dei numeri scelti a caso nello spazio a 63 bit ha il 63 ° bit impostato!

Sull'ingresso 0x3FFFFFFFFFFFFFFF, la versione ad albero delle decisioni è un po 'più veloce di quanto sia su 1, e mostra di essere il 1120% più veloce (12,2 volte) rispetto al bit shifter.

Analizzerò anche l'albero decisionale contro i builtin GCC, e tenterò anche una combinazione di input piuttosto che ripetere contro lo stesso numero. Potrebbe esserci qualche previsione di branching in corso e forse alcuni scenari di caching non realistici che lo rendono artificialmente più veloce nelle ripetizioni.

Che dire

 int highest_bit(unsigned int a) { int count; std::frexp(a, &count); return count - 1; } 

?

 unsigned int msb32(register unsigned int x) { x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); return(x & ~(x >> 1)); } 

1 registro, 13 istruzioni. Che ci crediate o no, questo è solitamente più veloce dell’istruzione BSR sopra menzionata, che opera in tempo lineare. Questo è il tempo logaritmico.

Da http://aggregate.org/MAGIC/#Most%20Significant%201%20Bit

Ecco alcuni (semplici) benchmark, di algoritmi attualmente forniti in questa pagina …

Gli algoritmi non sono stati testati su tutti gli input di unsigned int; quindi controlla prima, prima di usare ciecamente qualcosa;)

Sulla mia macchina clz (__builtin_clz) e asm funzionano meglio. asm sembra ancora più veloce di clz … ma potrebbe essere dovuto al semplice benchmark …

 //////// go.c /////////////////////////////// // compile with: gcc go.c -o go -lm #include  #include  #include  #include  

Anche se probabilmente userò questo metodo solo se ho assolutamente richiesto le migliori prestazioni possibili (ad es. Per scrivere una sorta di IA di gioco da tavolo che coinvolge bitboard), la soluzione più efficiente è usare ASM in linea. Vedi la sezione Ottimizzazioni di questo post del blog per il codice con una spiegazione.

[…], l’istruzione di assemblaggio di bsrl calcola la posizione del bit più significativo. Quindi, potremmo usare questa affermazione asm :

 asm ("bsrl %1, %0" : "=r" (position) : "r" (number)); 

Avevo bisogno di una routine per farlo e prima di cercare sul web (e trovando questa pagina) ho trovato la mia soluzione basata su una ricerca binaria. Anche se sono sicuro che qualcuno l’abbia già fatto prima! Funziona in un tempo costante e può essere più veloce della soluzione “ovvia” pubblicata, anche se non sto facendo grandi reclami, semplicemente pubblicandolo per interesse.

 int highest_bit(unsigned int a) { static const unsigned int maskv[] = { 0xffff, 0xff, 0xf, 0x3, 0x1 }; const unsigned int *mask = maskv; int l, h; if (a == 0) return -1; l = 0; h = 32; do { int m = l + (h - l) / 2; if ((a >> m) != 0) l = m; else if ((a & (*mask < < l)) != 0) h = m; mask++; } while (l < h - 1); return l; } 

Come indicato nelle risposte precedenti, ci sono diversi modi per determinare il bit più significativo. Tuttavia, come è stato anche sottolineato, è probabile che i metodi siano unici per i registri a 32 bit o 64 bit. La pagina stanford.edu bithacks fornisce soluzioni che funzionano sia per il computing a 32 bit che a 64 bit. Con un po ‘di lavoro, possono essere combinati per fornire un solido approccio cross-architecture per ottenere l’MSB. La soluzione alla quale sono arrivato è stata compilata / elaborata su computer a 64 e 32 bit:

 #if defined(__LP64__) || defined(_LP64) # define BUILD_64 1 #endif #include  #include  /* for uint32_t */ /* CHAR_BIT (or include limits.h) */ #ifndef CHAR_BIT #define CHAR_BIT 8 #endif /* CHAR_BIT */ /* * Find the log base 2 of an integer with the MSB N set in O(N) * operations. (on 64bit & 32bit architectures) */ int getmsb (uint32_t word) { int r = 0; if (word < 1) return 0; #ifdef BUILD_64 union { uint32_t u[2]; double d; } t; // temp tu[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000; tu[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = word; td -= 4503599627370496.0; r = (tu[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF; #else while (word >>= 1) { r++; } #endif /* BUILD_64 */ return r; } 

Una versione in C usando approssimazione successiva:

 unsigned int getMsb(unsigned int n) { unsigned int msb = sizeof(n) * 4; unsigned int step = msb; while (step > 1) { step /=2; if (n>>msb) msb += step; else msb -= step; } if (n>>msb) msb++; return (msb - 1); } 

Vantaggio: il tempo di esecuzione è costante indipendentemente dal numero fornito, poiché il numero di loop è sempre lo stesso. (4 loop quando si usa “unsigned int”)

questo è un tipo di ricerca binaria, funziona con tutti i tipi di tipi interi (non firmati!)

 #include  #define UINT (unsigned int) #define UINT_BIT (CHAR_BIT*sizeof(UINT)) int msb(UINT x) { if(0 == x) return -1; int c = 0; for(UINT i=UINT_BIT>>1; 0>=1) if(static_cast(x >> i)) { x >>= i; c |= i; } return c; } 

per completare:

 #include  #define UINT unsigned int #define UINT_BIT (CHAR_BIT*sizeof(UINT)) int lsb(UINT x) { if(0 == x) return -1; int c = UINT_BIT-1; for(UINT i=UINT_BIT>>1; 0>=1) if(static_cast(x < < i)) { x <<= i; c ^= i; } return c; } 

Alcune risposte troppo complesse qui. La tecnica Debruin dovrebbe essere usata solo quando l’input è già una potenza di due, altrimenti c’è un modo migliore. Per una potenza di 2 ingressi, Debruin è il più veloce, persino più veloce di _BitScanReverse su qualsiasi processore che ho testato. Tuttavia, nel caso generale, _BitScanReverse (o qualunque cosa l’intrinseco viene chiamato nel compilatore) è il più veloce (su certe CPU può essere microcodificato).

Se la funzione intrinseca non è un’opzione, qui è una soluzione software ottimale per elaborare gli input generali.

 u8 inline log2 (u32 val) { u8 k = 0; if (val > 0x0000FFFFu) { val >>= 16; k = 16; } if (val > 0x000000FFu) { val >>= 8; k |= 8; } if (val > 0x0000000Fu) { val >>= 4; k |= 4; } if (val > 0x00000003u) { val >>= 2; k |= 2; } k |= (val & 2) >> 1; return k; } 

Si noti che questa versione non richiede una ricerca Debruin alla fine, a differenza della maggior parte delle altre risposte. Calcola la posizione sul posto.

Le tabelle possono essere preferibili anche se, se la chiami ripetutamente abbastanza volte, il rischio di una mancanza della cache viene eclissato dall’accelerazione di una tabella.

 u8 kTableLog2[256] = { 0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7 }; u8 log2_table(u32 val) { u8 k = 0; if (val > 0x0000FFFFuL) { val >>= 16; k = 16; } if (val > 0x000000FFuL) { val >>= 8; k |= 8; } k |= kTableLog2[val]; // precompute the Log2 of the low byte return k; } 

Questo dovrebbe produrre il throughput più alto di una qualsiasi delle risposte del software fornite qui, ma se lo chiami solo occasionalmente, preferisci una soluzione senza tabella come il mio primo frammento di codice.

c99 has given us log2 . This removes the need for all the special sauce log2 implementations you see on this page. You can use the standard’s log2 implementation like this:

 const auto n = 13UL; const auto Index = (unsigned long)log2(n); printf("MSB is: %u\n", Index); // Prints 3 (zero offset) 

An n of 0UL needs to be guarded against as well, because:

-∞ is returned and FE_DIVBYZERO is raised

I have written an example with that check that arbitrarily sets Index to ULONG_MAX here: https://ideone.com/u26vsi


The visual-studio corollary to ephemient’s gcc only answer is:

 const auto n = 13UL; unsigned long Index; _BitScanReverse(&Index, n); printf("MSB is: %u\n", Index); // Prints 3 (zero offset) 

The documentation for _BitScanReverse states that Index is:

Loaded with the bit position of the first set bit (1) found

In practice I’ve found that if n is 0UL that Index is set to 0UL , just as it would be for an n of 1UL . But the only thing guaranteed in the documentation in the case of an n of 0UL is that the return is:

0 if no set bits were found

Thus, similarly to the preferable log2 implementation above the return should be checked setting Index to a flagged value in this case. I’ve again written an example of using ULONG_MAX for this flag value here: http://rextester.com/GCU61409

Think bitwise operators.

I missunderstood the question the first time. You should produce an int with the leftmost bit set (the others zero). Assuming cmp is set to that value:

 position = sizeof(int)*8 while(!(n & cmp)){ n < <=1; position--; } 

Expanding on Josh’s benchmark… one can improve the clz as follows

 /***************** clz2 ********************/ #define NUM_OF_HIGHESTBITclz2(a) ((a) \ ? (((1U) < < (sizeof(unsigned)*8-1)) >> __builtin_clz(a)) \ : 0) 

Regarding the asm: note that there are bsr and bsrl (this is the “long” version). the normal one might be a bit faster.

Note that what you are trying to do is calculate the integer log2 of an integer,

 #include  #include  unsigned int Log2(unsigned long x) { unsigned long n = x; int bits = sizeof(x)*8; int step = 1; int k=0; for( step = 1; step < bits; ) { n |= (n >> step); step *= 2; ++k; } //printf("%ld %ld\n",x, (x - (n >> 1)) ); return(x - (n >> 1)); } 

Observe that you can attempt to search more than 1 bit at a time.

 unsigned int Log2_a(unsigned long x) { unsigned long n = x; int bits = sizeof(x)*8; int step = 1; int step2 = 0; //observe that you can move 8 bits at a time, and there is a pattern... //if( x>1< 1< 1< 1L< 1L< <(step+step2); ) { step+=1; //printf("step %d\n",step+step2); } printf("log2(%ld) %d\n",x,step+step2); return(step+step2); } 

This approach uses a binary search

 unsigned int Log2_b(unsigned long x) { unsigned long n = x; unsigned int bits = sizeof(x)*8; unsigned int hbit = bits-1; unsigned int lbit = 0; unsigned long guess = bits/2; int found = 0; while ( hbit-lbit>1 ) { //printf("log2(%ld) %d< %d<%d\n",x,lbit,guess,hbit); //when value between guess..lbit if( (x<=(1L<(1L<  1< <%d %ld\n",x,guess,1L<(1L<  

Another binary search method, perhaps more readable,

 unsigned int Log2_c(unsigned long x) { unsigned long v = x; unsigned int bits = sizeof(x)*8; unsigned int step = bits; unsigned int res = 0; for( step = bits/2; step>0; ) { //printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step); while ( v>>step ) { v>>=step; res+=step; //printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v); } step /= 2; } if( (x>(1L<  

And because you will want to test these,

 int main() { unsigned long int x = 3; for( x=2; x<1000000000; x*=2 ) { //printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1)); printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1)); printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1)); printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1)); } return(0); } 

Putting this in since it’s ‘yet another’ approach, seems to be different from others already given.

returns -1 if x==0 , otherwise floor( log2(x)) (max result 31)

Reduce from 32 to 4 bit problem, then use a table. Perhaps inelegant, but pragmatic.

This is what I use when I don’t want to use __builtin_clz because of portability issues.

To make it more compact, one could instead use a loop to reduce, adding 4 to r each time, max 7 iterations. Or some hybrid, such as (for 64 bits): loop to reduce to 8, test to reduce to 4.

 int log2floor( unsigned x ){ static const signed char wtab[16] = {-1,0,1,1, 2,2,2,2, 3,3,3,3,3,3,3,3}; int r = 0; unsigned xk = x >> 16; if( xk != 0 ){ r = 16; x = xk; } // x is 0 .. 0xFFFF xk = x >> 8; if( xk != 0){ r += 8; x = xk; } // x is 0 .. 0xFF xk = x >> 4; if( xk != 0){ r += 4; x = xk; } // now x is 0..15; x=0 only if originally zero. return r + wtab[x]; } 

I know this question is very old, but just having implemented an msb() function myself, I found that most solutions presented here and on other websites are not necessarily the most efficient – at least for my personal definition of efficiency (see also Update below). Ecco perché:

Most solutions (especially those which employ some sort of binary search scheme or the naïve approach which does a linear scan from right to left) seem to neglect the fact that for arbitrary binary numbers, there are not many which start with a very long sequence of zeros. In fact, for any bit-width, half of all integers start with a 1 and a quarter of them start with 01 . See where i’m getting at? My argument is that a linear scan starting from the most significant bit position to the least significant (left to right) is not so “linear” as it might look like at first glance.

It can be shown 1 , that for any bit-width, the average number of bits that need to be tested is at most 2. This translates to an amortized time complexity of O(1) with respect to the number of bits (!).

Of course, the worst case is still O(n) , worse than the O(log(n)) you get with binary-search-like approaches, but since there are so few worst cases, they are negligible for most applications ( Update : not quite: There may be few, but they might occur with high probability – see Update below).

Here is the “naïve” approach i’ve come up with, which at least on my machine beats most other approaches (binary search schemes for 32-bit ints always require log 2 (32) = 5 steps, whereas this silly algorithm requires less than 2 on average) – sorry for this being C++ and not pure C:

 template  auto msb(T n) -> int { static_assert(std::is_integral::value && !std::is_signed::value, "msb(): T must be an unsigned integral type."); for (T i = std::numeric_limits::digits - 1, mask = 1 < < i; i >= 0; --i, mask >>= 1) { if ((n & mask) != 0) return i; } return 0; } 

Update : While what i wrote here is perfectly true for arbitrary integers, where every combination of bits is equally probable (my speed test simply measured how long it took to determine the MSB for all 32-bit integers), real-life integers, for which such a function will be called, usually follow a different pattern: In my code, for example, this function is used to determine whether an object size is a power of 2, or to find the next power of 2 greater or equal than an object size . My guess is that most applications using the MSB involve numbers which are much smaller than the maximum number an integer can represent (object sizes rarely utilize all the bits in a size_t ). In this case, my solution will actually perform worse than a binary search approach – so the latter should probably be preferred, even though my solution will be faster looping through all integers.
TL;DR: Real-life integers will probably have a bias towards the worst case of this simple algorithm, which will make it perform worse in the end – despite the fact that it’s amortized O(1) for truly arbitrary integers.

1 The argument goes like this (rough draft): Let n be the number of bits (bit-width). There are a total of 2 n integers wich can be represented with n bits. There are 2 n – 1 integers starting with a 1 (first 1 is fixed, remaining n – 1 bits can be anything). Those integers require only one interation of the loop to determine the MSB. Further, There are 2 n – 2 integers starting with 01 , requiring 2 iterations, 2 n – 3 integers starting with 001 , requiring 3 iterations, and so on.

If we sum up all the required iterations for all possible integers and divide them by 2 n , the total number of integers, we get the average number of iterations needed for determining the MSB for n -bit integers:

(1 * 2 n – 1 + 2 * 2 n – 2 + 3 * 2 n – 3 + … + n) / 2 n

This series of average iterations is actually convergent and has a limit of 2 for n towards infinity

Thus, the naïve left-to-right algorithm has actually an amortized constant time complexity of O(1) for any number of bits.

Il codice:

  // x>=1; unsigned func(unsigned x) { double d = x ; int p= (*reinterpret_cast(&d) >> 52) - 1023; printf( "The left-most non zero bit of %d is bit %d\n", x, p); } 

Or get the integer part of FPU instruction FYL2X (Y*Log2 X) by setting Y=1

Woaw, that was many answers. I am not sorry for answering on an old question.

 int result = 0;//could be a char or int8_t instead if(value){//this assumes the value is 64bit if(0xFFFFFFFF00000000&value){ value>>=(1< <5); result|=(1<<5); }//if it is 32bit then remove this line if(0x00000000FFFF0000&value){ value>>=(1< <4); result|=(1<<4); }//and remove the 32msb if(0x000000000000FF00&value){ value>>=(1< <3); result|=(1<<3); } if(0x00000000000000F0&value){ value>>=(1< <2); result|=(1<<2); } if(0x000000000000000C&value){ value>>=(1< <1); result|=(1<<1); } if(0x0000000000000002&value){ result|=(1<<0); } }else{ result=-1; } 

This answer is pretty similar to another answer... oh well.

I assume your question is for an integer (called v below) and not an unsigned integer.

 int v = 612635685; // whatever value you wish unsigned int get_msb(int v) { int r = 31; // maximum number of iteration until integer has been totally left shifted out, considering that first bit is index 0. Also we could use (sizeof(int)) < < 3 - 1 instead of 31 to make it work on any platform. while (!(v & 0x8000000) && r--) { // mask of the highest bit v <<= 1; // multiply integer by 2. } return r; // will even return -1 if no bit was set, allowing error catch } 

If you want to make it work without taking into account the sign you can add an extra 'v < <= 1;' before the loop (and change r value to 30 accordingly). Please let me know if I forgot anything. I haven't tested it but it should work just fine.

Another poster provided a lookup-table using a byte-wide lookup. In case you want to eke out a bit more performance (at the cost of 32K of memory instead of just 256 lookup entries) here is a solution using a 15-bit lookup table , in C# 7 for .NET .

The interesting part is initializing the table. Since it’s a relatively small block that we want for the lifetime of the process, I allocate unmanaged memory for this by using Marshal.AllocHGlobal . As you can see, for maximum performance, the whole example is written as native:

 readonly static byte[] msb_tab_15; // Initialize a table of 32768 bytes with the bit position (counting from LSB=0) // of the highest 'set' (non-zero) bit of its corresponding 16-bit index value. // The table is compressed by half, so use (value >> 1) for indexing. static MyStaticInit() { var p = new byte[0x8000]; for (byte n = 0; n < 16; n++) for (int c = (1 << n) >> 1, i = 0; i < c; i++) p[c + i] = n; msb_tab_15 = p; } 

The table requires one-time initialization via the code above. It is read-only so a single global copy can be shared for concurrent access. With this table you can quickly look up the integer log 2 , which is what we're looking for here, for all the various integer widths (8, 16, 32, and 64 bits).

Notice that the table entry for 0 , the sole integer for which the notion of 'highest set bit' is undefined, is given the value -1 . This distinction is necessary for proper handling of 0-valued upper words in the code below. Without further ado, here is the code for each of the various integer primitives:

ulong (64-bit) Version

 ///  Index of the highest set bit in 'v', or -1 for value '0'  public static int HighestOne(this ulong v) { if ((long)v < = 0) return (int)((v >> 57) & 0x40) - 1; // handles cases v==0 and MSB==63 int j = /**/ (int)((0xFFFFFFFFU - v /****/) >> 58) & 0x20; j |= /*****/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10; return j + msb_tab_15[v >> (j + 1)]; } 

uint (32-bit) Version

 ///  Index of the highest set bit in 'v', or -1 for value '0'  public static int HighestOne(uint v) { if ((int)v < = 0) return (int)((v >> 26) & 0x20) - 1; // handles cases v==0 and MSB==31 int j = (int)((0x0000FFFFU - v) >> 27) & 0x10; return j + msb_tab_15[v >> (j + 1)]; } 

Various overloads for the above

 public static int HighestOne(long v) => HighestOne((ulong)v); public static int HighestOne(int v) => HighestOne((uint)v); public static int HighestOne(ushort v) => msb_tab_15[v >> 1]; public static int HighestOne(short v) => msb_tab_15[(ushort)v >> 1]; public static int HighestOne(char ch) => msb_tab_15[ch >> 1]; public static int HighestOne(sbyte v) => msb_tab_15[(byte)v >> 1]; public static int HighestOne(byte v) => msb_tab_15[v >> 1]; 

This is a complete, working solution which represents the best performance on .NET 4.7.2 for numerous alternatives that I compared with a specialized performance test harness. Some of these are mentioned below. The test parameters were a uniform density of all 65 bit positions, ie, 0 ... 31/63 plus value 0 (which produces result -1). The bits below the target index position were filled randomly. The tests were x64 only, release mode, with JIT-optimizations enabled.

That's the end of my formal answer here; what follows are some casual notes and links to source code for alternative test candidates associated with the testing I ran to validate the performance and correctness of the above code.


The version provided above above, coded as Tab16A was a consistent winner over many runs. These various candidates, in active working/scratch form, can be found here , here , and here .

 1 candidates.HighestOne_Tab16A 622,496
 2 candidates.HighestOne_Tab16C 628,234
 3 candidates.HighestOne_Tab8A 649,146
 4 candidates.HighestOne_Tab8B 656,847
 5 candidates.HighestOne_Tab16B 657,147
 6 candidates.HighestOne_Tab16D 659,650
 7 _highest_one_bit_UNMANAGED.HighestOne_U 702,900
 8 de_Bruijn.IndexOfMSB 709,672
 9 _old_2.HighestOne_Old2 715,810
10 _test_A.HighestOne8 757,188
11 _old_1.HighestOne_Old1 757,925
12 _test_A.HighestOne5 (unsafe) 760,387
13 _test_B.HighestOne8 (unsafe) 763,904
14 _test_A.HighestOne3 (unsafe) 766,433
15 _test_A.HighestOne1 (unsafe) 767,321
16 _test_A.HighestOne4 (unsafe) 771,702
17 _test_B.HighestOne2 (unsafe) 772,136
18 _test_B.HighestOne1 (unsafe) 772,527
19 _test_B.HighestOne3 (unsafe) 774,140
20 _test_A.HighestOne7 (unsafe) 774,581
21 _test_B.HighestOne7 (unsafe) 775,463
22 _test_A.HighestOne2 (unsafe) 776,865
23 candidates.HighestOne_NoTab 777,698
24 _test_B.HighestOne6 (unsafe) 779,481
25 _test_A.HighestOne6 (unsafe) 781,553
26 _test_B.HighestOne4 (unsafe) 785,504
27 _test_B.HighestOne5 (unsafe) 789,797
28 _test_A.HighestOne0 (unsafe) 809,566
29 _test_B.HighestOne0 (unsafe) 814,990
30 _highest_one_bit.HighestOne 824,345
30 _bitarray_ext.RtlFindMostSignificantBit 894,069
31 candidates.HighestOne_Naive 898,865 

Notable is that the terrible performance of ntdll.dll!RtlFindMostSignificantBit via P/Invoke:

 [DllImport("ntdll.dll"), SuppressUnmanagedCodeSecurity, SecuritySafeCritical] public static extern int RtlFindMostSignificantBit(ulong ul); 

It's really too bad, because here's the entire actual function:

  RtlFindMostSignificantBit: bsr rdx, rcx mov eax,0FFFFFFFFh movzx ecx, dl cmovne eax,ecx ret 

I can't imagine the poor performance originating with these five lines, so the managed/native transition penalties must be to blame. I was also surprised that the testing really favored the 32KB (and 64KB) short (16-bit) direct-lookup tables over the 128-byte (and 256-byte) byte (8-bit) lookup tables. I thought the following would be more competitive with the 16-bit lookups, but the latter consistently outperformsd this:

 public static int HighestOne_Tab8A(ulong v) { if ((long)v < = 0) return (int)((v >> 57) & 64) - 1; int j; j = /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32; j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16; j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8; return j + msb_tab_8[v >> j]; } 

The last thing I'll point out is that I was quite shocked that my deBruijn method didn't fare better. This is the method that I had previously been using pervasively:

 const ulong N_bsf64 = 0x07EDD5E59A4E28C2, N_bsr64 = 0x03F79D71B4CB0A89; readonly public static sbyte[] bsf64 = { 63, 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56, 45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, }, bsr64 = { 0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61, 54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62, 46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45, 25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63, }; public static int IndexOfLSB(ulong v) => v != 0 ? bsf64[((v & (ulong)-(long)v) * N_bsf64) >> 58] : -1; public static int IndexOfMSB(ulong v) { if ((long)v < = 0) return (int)((v >> 57) & 64) - 1; v |= v >> 1; v |= v >> 2; v |= v >> 4; // does anybody know a better v |= v >> 8; v |= v >> 16; v |= v >> 32; // way than these 12 ops? return bsr64[(v * N_bsr64) >> 58]; } 

There's much discussion of how superior and great deBruijn methods at this SO question , and I had tended to agree. My speculation is that, while both the deBruijn and direct lookup table methods (that I found to be fastest) both have to do a table lookup, and both have very minimal branching, only the deBruijn has a 64-bit multiply operation. I only tested the IndexOfMSB functions here--not the deBruijn IndexOfLSB --but I expect the latter to fare much better chance since it has so many fewer operations (see above), and I'll likely continue to use it for LSB.

One approach could be to keep shifting left till the number becomes negative.

Ecco il codice:

 Funct() { int number; int count; while(number > 0) { number = number < < 1; count++; } printf("It is the no "%d" bit from the left", (count+1)); }