tabla - ¿Cuál es la forma más rápida/más eficiente de encontrar el bit más alto establecido(msb) en un entero en C?
tipos de datos primitivos en c (26)
Si tengo un entero n, y quiero saber la posición del bit más significativo (es decir, si el bit menos significativo está a la derecha, quiero saber la posición del bit más a la izquierda que es un 1), ¿Cuál es el método más rápido / más eficiente para descubrir?
Sé que POSIX admite un método ffs ffs() en strings.h para encontrar el primer bit configurado, pero no parece haber un método fls() correspondiente.
¿Hay alguna manera realmente obvia de hacer esto que me estoy perdiendo?
¿Qué pasa si no puede usar las funciones POSIX para la portabilidad?
Editar: ¿Qué pasa con una solución que funciona en las arquitecturas de 32 y 64 bits (muchos de los listados de códigos parecen que solo funcionarían en las entradas de 32 bits).
Algunas respuestas demasiado complejas aquí. La técnica Debruin solo debe usarse cuando la entrada ya es una potencia de dos; de lo contrario, hay una mejor manera. Para una potencia de 2 entradas, Debruin es el más rápido absoluto, incluso más rápido que _BitScanReverse en cualquier procesador que he probado. Sin embargo, en el caso general, _BitScanReverse (o lo que se llame intrínseco en su compilador) es el más rápido (en ciertas CPU, sin embargo, puede ser microcodificado).
Si la función intrínseca no es una opción, aquí hay una solución de software óptima para procesar entradas generales.
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;
}
Tenga en cuenta que esta versión no requiere una búsqueda de Debruin al final, a diferencia de la mayoría de las otras respuestas. Calcula la posición en su lugar.
Las tablas pueden ser preferibles, sin embargo, si lo llamas varias veces lo suficiente, el riesgo de una falta de caché se ve eclipsado por la aceleración de una tabla.
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;
}
This should produce the highest throughput of any of the software answers given here, but if you only call it occasionally, prefer a table-free solution like my first snippet.
Aquí hay algunos puntos de referencia (simples), de los algoritmos que se dan actualmente en esta página ...
Los algoritmos no se han probado en todas las entradas de unsigned int; así que revisen eso primero, antes de usar ciegamente algo;)
En mi máquina clz (__builtin_clz) y asm funcionan mejor. asm parece incluso más rápido que clz ... pero podría deberse a la referencia simple ...
//////// go.c ///////////////////////////////
// compile with: gcc go.c -o go -lm
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/***************** math ********************/
#define POS_OF_HIGHESTBITmath(a) /* 0th position is the Least-Signif-Bit */ /
((unsigned) log2(a)) /* thus: do not use if a <= 0 */
#define NUM_OF_HIGHESTBITmath(a) ((a) /
? (1U << POS_OF_HIGHESTBITmath(a)) /
: 0)
/***************** clz ********************/
unsigned NUM_BITS_U = ((sizeof(unsigned) << 3) - 1);
#define POS_OF_HIGHESTBITclz(a) (NUM_BITS_U - __builtin_clz(a)) /* only works for a != 0 */
#define NUM_OF_HIGHESTBITclz(a) ((a) /
? (1U << POS_OF_HIGHESTBITclz(a)) /
: 0)
/***************** i2f ********************/
double FF;
#define POS_OF_HIGHESTBITi2f(a) (FF = (double)(ui|1), ((*(1+(unsigned*)&FF))>>20)-1023)
#define NUM_OF_HIGHESTBITi2f(a) ((a) /
? (1U << POS_OF_HIGHESTBITi2f(a)) /
: 0)
/***************** asm ********************/
unsigned OUT;
#define POS_OF_HIGHESTBITasm(a) (({asm("bsrl %1,%0" : "=r"(OUT) : "r"(a));}), OUT)
#define NUM_OF_HIGHESTBITasm(a) ((a) /
? (1U << POS_OF_HIGHESTBITasm(a)) /
: 0)
/***************** bitshift1 ********************/
#define NUM_OF_HIGHESTBITbitshift1(a) (({ /
OUT = a; /
OUT |= (OUT >> 1); /
OUT |= (OUT >> 2); /
OUT |= (OUT >> 4); /
OUT |= (OUT >> 8); /
OUT |= (OUT >> 16); /
}), (OUT & ~(OUT >> 1))) /
/***************** bitshift2 ********************/
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};
#define POS_OF_HIGHESTBITbitshift2(a) (({ /
OUT = a; /
OUT |= OUT >> 1; /
OUT |= OUT >> 2; /
OUT |= OUT >> 4; /
OUT |= OUT >> 8; /
OUT |= OUT >> 16; /
OUT = (OUT >> 1) + 1; /
}), POS[(OUT * 0x077CB531UL) >> 27])
#define NUM_OF_HIGHESTBITbitshift2(a) ((a) /
? (1U << POS_OF_HIGHESTBITbitshift2(a)) /
: 0)
#define LOOPS 100000000U
int main()
{
time_t start, end;
unsigned ui;
unsigned n;
/********* Checking the first few unsigned values (you''ll need to check all if you want to use an algorithm here) **************/
printf("math/n");
for (ui = 0U; ui < 18; ++ui)
printf("%i/t%i/n", ui, NUM_OF_HIGHESTBITmath(ui));
printf("/n/n");
printf("clz/n");
for (ui = 0U; ui < 18U; ++ui)
printf("%i/t%i/n", ui, NUM_OF_HIGHESTBITclz(ui));
printf("/n/n");
printf("i2f/n");
for (ui = 0U; ui < 18U; ++ui)
printf("%i/t%i/n", ui, NUM_OF_HIGHESTBITi2f(ui));
printf("/n/n");
printf("asm/n");
for (ui = 0U; ui < 18U; ++ui) {
printf("%i/t%i/n", ui, NUM_OF_HIGHESTBITasm(ui));
}
printf("/n/n");
printf("bitshift1/n");
for (ui = 0U; ui < 18U; ++ui) {
printf("%i/t%i/n", ui, NUM_OF_HIGHESTBITbitshift1(ui));
}
printf("/n/n");
printf("bitshift2/n");
for (ui = 0U; ui < 18U; ++ui) {
printf("%i/t%i/n", ui, NUM_OF_HIGHESTBITbitshift2(ui));
}
printf("/n/nPlease wait.../n/n");
/************************* Simple clock() benchmark ******************/
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITmath(ui);
end = clock();
printf("math:/t%e/n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITclz(ui);
end = clock();
printf("clz:/t%e/n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITi2f(ui);
end = clock();
printf("i2f:/t%e/n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITasm(ui);
end = clock();
printf("asm:/t%e/n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITbitshift1(ui);
end = clock();
printf("bitshift1:/t%e/n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITbitshift2(ui);
end = clock();
printf("bitshift2/t%e/n", (double)(end-start)/CLOCKS_PER_SEC);
printf("/nThe lower, the better. Take note that a negative exponent is good! ;)/n");
return EXIT_SUCCESS;
}
Aunque probablemente solo usaría este método si requiriera absolutamente el mejor rendimiento posible (por ejemplo, para escribir algún tipo de juego de mesa AI que implique tablas de bits), la solución más eficiente es usar ASM en línea. Consulte la sección de Optimizaciones de esta publicación de blog para obtener un código con una explicación.
[...], la instrucción de ensamblaje
bsrlcalcula la posición del bit más significativo. Por lo tanto, podríamos usar esta declaraciónasm:
asm ("bsrl %1, %0" : "=r" (position) : "r" (number));
Como 2 ^ N es un número entero con solo el Nth bit set (1 << N), encontrar la posición (N) del bit más alto establecido es la base de registro entero 2 de ese entero.
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
unsigned int v;
unsigned r = 0;
while (v >>= 1) {
r++;
}
Este algoritmo "obvio" puede no ser transparente para todos, pero cuando te das cuenta de que el código cambia un bit repetidamente hasta que el bit más a la izquierda haya sido desplazado (ten en cuenta que C trata cualquier valor distinto de cero como verdadero) y devuelve el número de turnos, tiene perfecto sentido. También significa que funciona incluso cuando se establece más de un bit, el resultado siempre es para el bit más significativo.
Si se desplaza hacia abajo en esa página, hay variaciones más rápidas y complejas. Sin embargo, si sabe que está tratando con números con muchos ceros a la izquierda, el enfoque ingenuo puede proporcionar una velocidad aceptable, ya que el cambio de bit es bastante rápido en C, y el algoritmo simple no requiere indexar una matriz.
NOTA: Cuando use valores de 64 bits, tenga mucho cuidado con el uso de algoritmos extra-inteligentes; muchos de ellos solo funcionan correctamente para valores de 32 bits.
Como las respuestas anteriores señalan, hay varias maneras de determinar el bit más significativo. Sin embargo, como también se señaló, es probable que los métodos sean únicos para los registros de 32 bits o de 64 bits. La http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious proporciona soluciones que funcionan tanto para computación de 32 bits como de 64 bits. Con un poco de trabajo, se pueden combinar para proporcionar un enfoque sólido de arquitectura cruzada para obtener el MSB. La solución a la que llegué que compiló / trabajó en computadoras de 64 y 32 bits fue:
#if defined(__LP64__) || defined(_LP64)
# define BUILD_64 1
#endif
#include <stdio.h>
#include <stdint.h> /* 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
t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = word;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;
#else
while (word >>= 1)
{
r++;
}
#endif /* BUILD_64 */
return r;
}
Esto debería ser muy rápido:
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];
}
Esto es como encontrar un tipo de registro de enteros. Hay algunos trucos, pero he creado mi propia herramienta para esto. El objetivo, por supuesto, es la velocidad.
¡Me doy cuenta de que la CPU ya tiene un detector de bits automático, que se utiliza para la conversión de enteros a flotantes! Entonces usa eso.
double ff=(double)(v|1);
return ((*(1+(uint32_t *)&ff))>>20)-1023; // assumes x86 endianness
Esta versión arroja el valor a un doble, luego lee el exponente, que le dice dónde estaba el bit. El elegante desplazamiento y resta es extraer las partes apropiadas del valor IEEE.
Es un poco más rápido usar flotadores, pero un flotador solo puede darle las primeras posiciones de 24 bits debido a su menor precisión.
Para hacer esto de manera segura, sin un comportamiento indefinido en C ++ o C, use memcpy lugar de punteo para memcpy de tipo. Los compiladores saben cómo alinearlo de manera eficiente.
// 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 en C99 y posterior, use una union {double d; uint32_t u[2];}; union {double d; uint32_t u[2];}; . Pero tenga en cuenta que en C ++, el tipo de unión de unión solo se admite en algunos compiladores como una extensión, no en ISO C ++.
Esto generalmente será más lento que un intrínseco específico de plataforma para una instrucción de conteo de ceros a la izquierda, pero el ISO portátil C no tiene esa función. Algunas CPU también carecen de una instrucción de conteo de cero principal, pero algunas de ellas pueden convertir de forma eficiente números enteros al double . Sin embargo, la repetición de tipos de un patrón de bits FP a entero puede ser lenta (por ejemplo, en PowerPC requiere una tienda / recarga y generalmente causa un bloqueo de carga en la tienda).
Este algoritmo podría ser útil para implementaciones SIMD, ya que menos CPU tienen SIMD lzcnt . x86 solo recibió una instrucción de este tipo con AVX512CD
Kaz Kylheku aquí
Analicé dos enfoques para este número de más de 63 bits (el tipo largo y largo en gcc x86_64), manteniéndome alejado del bit de signo.
(Por casualidad, necesito este "encontrar el bit más alto" para algo, ya ves).
Implementé la búsqueda binaria basada en datos (muy basada en una de las respuestas anteriores). También implementé un árbol de decisión completamente desenrollado a mano, que es solo código con operandos inmediatos. Sin bucles, sin tablas.
El árbol de decisión (highest_bit_unrolled) se calculó como 69% más rápido, excepto para el caso n = 0 para el cual la búsqueda binaria tiene una prueba explícita.
La prueba especial de búsqueda binaria para 0 casos es solo un 48% más rápida que el árbol de decisiones, que no tiene una prueba especial.
Compilador, máquina: (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;
}
Programa de prueba rápido y sucio:
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int highest_bit_unrolled(long long n);
int highest_bit(long long n);
main(int argc, char **argv)
{
long long n = strtoull(argv[1], NULL, 0);
int b1, b2;
long i;
clock_t start = clock(), mid, end;
for (i = 0; i < 1000000000; i++)
b1 = highest_bit_unrolled(n);
mid = clock();
for (i = 0; i < 1000000000; i++)
b2 = highest_bit(n);
end = clock();
printf("highest bit of 0x%llx/%lld = %d, %d/n", n, n, b1, b2);
printf("time1 = %d/n", (int) (mid - start));
printf("time2 = %d/n", (int) (end - mid));
return 0;
}
Usando solo -O2, la diferencia se vuelve mayor. El árbol de decisión es casi cuatro veces más rápido.
También comparé contra el código ingenuo de cambio de bit:
int highest_bit_shift(long long n)
{
int i = 0;
for (; n; n >>= 1, i++)
; /* empty */
return i;
}
Esto es solo rápido para números pequeños, como uno esperaría. Al determinar que el bit más alto es 1 para n == 1, se comparó más del 80% más rápido. Sin embargo, ¡la mitad de los números elegidos al azar en el espacio de 63 bits tienen el bit 63 establecido!
En la entrada 0x3FFFFFFFFFFFFFFF, la versión del árbol de decisión es bastante más rápida que en el 1, y muestra que es 1120% más rápida (12,2 veces) que la del bit shifter.
También compararé el árbol de decisiones con las construcciones internas de CCG, y también probaré una combinación de entradas en lugar de repetir con el mismo número. Puede haber alguna predicción de bifurcación continua y quizás algunos escenarios de almacenamiento en caché poco realistas que la hagan artificialmente más rápida en las repeticiones.
Necesitaba una rutina para hacer esto y antes de buscar en la web (y encontrar esta página) se me ocurrió una solución propia basada en una búsqueda binaria. ¡Aunque estoy seguro de que alguien ha hecho esto antes! Funciona en tiempo constante y puede ser más rápido que la solución "obvia" publicada, aunque no estoy haciendo ningún gran reclamo, solo lo publico por interés.
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;
}
Qué pasa
int highest_bit(unsigned int a) {
int count;
std::frexp(a, &count);
return count - 1;
}
?
Suponiendo que está en x86 y juego para un poco de ensamblador en línea, Intel proporciona una instrucción BSR ("exploración de bits inversa"). Es fast en algunos x86 (microcodificado en otros). Del manual:
Busca el operando de origen para el bit establecido más significativo (1 bit). Si se encuentra uno de los más significativos, su índice de bits se almacena en el operando de destino. El operando de origen puede ser un registro o una ubicación de memoria; el operando de destino es un registro. El índice de bits es un desplazamiento sin signo del bit 0 del operando de origen. Si el operando fuente de contenido es 0, el contenido del operando de destino no está definido.
(Si está en PowerPC hay una cntlz similar ("count leading ceros").)
Código de ejemplo para gcc:
#include <iostream>
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;
}
Ver también este tutorial de ensamblador en línea , que muestra (sección 9.4) que es considerablemente más rápido que el código de bucle.
Una versión en C que usa una aproximación sucesiva:
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);
}
Ventaja: el tiempo de ejecución es constante independientemente del número proporcionado, ya que el número de bucles siempre es el mismo. (4 bucles cuando se usa "unsigned int")
eso es algún tipo de búsqueda binaria, funciona con todo tipo de tipos enteros (¡sin firmar!)
#include <climits>
#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<i; i>>=1)
if(static_cast<UINT>(x >> i))
{
x >>= i;
c |= i;
}
return c;
}
hacer completo:
#include <climits>
#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<i; i>>=1)
if(static_cast<UINT>(x << i))
{
x <<= i;
c ^= i;
}
return c;
}
-- Built-in Function: int __builtin_clz (unsigned int x) Returns the number of leading 0-bits in X, starting at the most significant bit position. If X is 0, the result is undefined. -- Built-in Function: int __builtin_clzl (unsigned long) Similar to `__builtin_clz'', except the argument type is `unsigned long''. -- Built-in Function: int __builtin_clzll (unsigned long long) Similar to `__builtin_clz'', except the argument type is `unsigned long long''.
Esperaría que se tradujeran en algo razonablemente eficiente para su plataforma actual, ya sea uno de esos sofisticados algoritmos de intercambio de bits o una sola instrucción.
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
/// <summary> Index of the highest set bit in ''v'', or -1 for value ''0'' </summary>
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
/// <summary> Index of the highest set bit in ''v'', or -1 for value ''0'' </summary>
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 outperformed 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.
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.
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.
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). Este es el por qué:
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 <typename T>
auto msb(T n) -> int
{
static_assert(std::is_integral<T>::value && !std::is_signed<T>::value,
"msb<T>(): T must be an unsigned integral type.");
for (T i = std::numeric_limits<T>::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.
Note that what you are trying to do is calculate the integer log2 of an integer,
#include <stdio.h>
#include <stdlib.h>
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<<step2+8 ) { step2+=8;
//if( x>1<<step2+8 ) { step2+=8;
//if( x>1<<step2+8 ) { step2+=8;
//}
//}
//}
for( step2=0; x>1L<<step2+8; ) {
step2+=8;
}
//printf("step2 %d/n",step2);
for( step = 0; x>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<<guess)) ) {
//printf("%ld < 1<<%d %ld/n",x,guess,1L<<guess);
hbit=guess;
guess=(hbit+lbit)/2;
//printf("log2(%ld) %d<%d<%d/n",x,lbit,guess,hbit);
}
//when value between hbit..guess
//else
if( (x>(1L<<guess)) ) {
//printf("%ld > 1<<%d %ld/n",x,guess,1L<<guess);
lbit=guess;
guess=(hbit+lbit)/2;
//printf("log2(%ld) %d<%d<%d/n",x,lbit,guess,hbit);
}
}
if( (x>(1L<<guess)) ) ++guess;
printf("log2(x%ld)=r%d/n",x,guess);
return(guess);
}
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<<res)) ) ++res;
printf("log2(x%ld)=r%ld/n",x,res);
return(res);
}
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);
}
One approach could be to keep shifting left till the number becomes negative.
Aquí está el código:
Funct() {
int number; int count;
while(number > 0) {
number = number << 1;
count++;
}
printf("It is the no "%d" bit from the left", (count+1));
}
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];
}
The code:
// x>=1;
unsigned func(unsigned x) {
double d = x ;
int p= (*reinterpret_cast<long long*>(&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
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--;
}
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.
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
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 instrucciones. Créalo o no, esto es generalmente más rápido que la instrucción BSR mencionada anteriormente, que opera en tiempo lineal. Este es el tiempo logarítmico.