programacion - Encuentra el bit de orden más alto en C

bit type c

Question

lo que busco es algo en lo que pueda alimentar un número y devolverá el bit de mayor orden. Estoy seguro de que hay una manera simple. A continuación se muestra un ejemplo de salida (a la izquierda está la entrada)

1 -> 1 2 -> 2 3 -> 2 4 -> 4 5 -> 4 6 -> 4 7 -> 4 8 -> 8 9 -> 8 ... 63 -> 32

Answer 1

¿Por qué no simplemente hacer esto?

int HiBit(int num){ return (num & 0x80000000) >> 31; }

Answer 2

Continuamente eliminar el bit de orden inferior viene a la mente ...

int highest_order_bit( int x )
{
int y = x;
do {
x = y;
y = x & (x-1); //remove low order bit
}
while( y != 0 );
return x;
}

Answer 3

De Hacker''s Delight:

int hibit(unsigned int n) {
n |= (n >> 1);
n |= (n >> 2);
n |= (n >> 4);
n |= (n >> 8);
n |= (n >> 16);
return n - (n >> 1);
}

Esta versión es para entradas de 32 bits, pero la lógica puede ampliarse para 64 bits o más.

Answer 4

El kernel de Linux tiene una cantidad de bits útiles como este, codificados de la manera más eficiente para varias arquitecturas. Puede encontrar versiones genéricas en include/asm-generic/bitops/fls.h (y amigos), pero vea también include/asm-x86/bitops.h para una definición que utiliza ensamblaje en línea si la velocidad es esencial y la portabilidad es no.

Answer 5

Esto debería funcionar.

int hob (int num)
{
if (!num)
return 0;
int ret = 1;
while (num >>= 1)
ret <<= 1;
return ret;
}

la encimera (1234) devuelve 1024
la encimera (1024) devuelve 1024
la encimera (1023) devuelve 512

Answer 6

Esto se puede resolver fácilmente con las llamadas a bibliotecas existentes.

int highestBit(int v){
return fls(v) << 1;
}

La página man de Linux proporciona más detalles sobre esta función y sus contrapartidas para otros tipos de entrada.

Answer 7

Si no necesita una solución portátil y su código se está ejecutando en una CPU compatible con x86, puede usar la función intrínseca _BitScanReverse () proporcionada por el compilador de Microsoft Visual C / C ++. Se asigna a la instrucción de CPU BSR que devuelve el conjunto de bits más alto.

Answer 8

Un poco tarde para esta fiesta, pero la solución más simple que encontré, dado un GCC moderno como compilador, es simplemente:

static inline int_t get_msb32 (register unsigned int val)
{
return 32 - __builtin_clz(val);
}
static inline int get_msb64 (register unsigned long long val)
{
return 64 - __builtin_clzll(val);
}

Incluso es relativamente portátil (al menos funcionará en cualquier plataforma de GCC).

Answer 9

Una forma rápida de hacerlo es a través de una tabla de búsqueda. Para una entrada de 32 bits y una tabla de búsqueda de 8 bits, solo requiere 4 iteraciones:

int highest_order_bit(int x)
{
static const int msb_lut[256] =
{
0, 0, 1, 1, 2, 2, 2, 2, // 0000_0000 - 0000_0111
3, 3, 3, 3, 3, 3, 3, 3, // 0000_1000 - 0000_1111
4, 4, 4, 4, 4, 4, 4, 4, // 0001_0000 - 0001_0111
4, 4, 4, 4, 4, 4, 4, 4, // 0001_1000 - 0001_1111
5, 5, 5, 5, 5, 5, 5, 5, // 0010_0000 - 0010_0111
5, 5, 5, 5, 5, 5, 5, 5, // 0010_1000 - 0010_1111
5, 5, 5, 5, 5, 5, 5, 5, // 0011_0000 - 0011_0111
5, 5, 5, 5, 5, 5, 5, 5, // 0011_1000 - 0011_1111
6, 6, 6, 6, 6, 6, 6, 6, // 0100_0000 - 0100_0111
6, 6, 6, 6, 6, 6, 6, 6, // 0100_1000 - 0100_1111
6, 6, 6, 6, 6, 6, 6, 6, // 0101_0000 - 0101_0111
6, 6, 6, 6, 6, 6, 6, 6, // 0101_1000 - 0101_1111
6, 6, 6, 6, 6, 6, 6, 6, // 0110_0000 - 0110_0111
6, 6, 6, 6, 6, 6, 6, 6, // 0110_1000 - 0110_1111
6, 6, 6, 6, 6, 6, 6, 6, // 0111_0000 - 0111_0111
6, 6, 6, 6, 6, 6, 6, 6, // 0111_1000 - 0111_1111
7, 7, 7, 7, 7, 7, 7, 7, // 1000_0000 - 1000_0111
7, 7, 7, 7, 7, 7, 7, 7, // 1000_1000 - 1000_1111
7, 7, 7, 7, 7, 7, 7, 7, // 1001_0000 - 1001_0111
7, 7, 7, 7, 7, 7, 7, 7, // 1001_1000 - 1001_1111
7, 7, 7, 7, 7, 7, 7, 7, // 1010_0000 - 1010_0111
7, 7, 7, 7, 7, 7, 7, 7, // 1010_1000 - 1010_1111
7, 7, 7, 7, 7, 7, 7, 7, // 1011_0000 - 1011_0111
7, 7, 7, 7, 7, 7, 7, 7, // 1011_1000 - 1011_1111
7, 7, 7, 7, 7, 7, 7, 7, // 1100_0000 - 1100_0111
7, 7, 7, 7, 7, 7, 7, 7, // 1100_1000 - 1100_1111
7, 7, 7, 7, 7, 7, 7, 7, // 1101_0000 - 1101_0111
7, 7, 7, 7, 7, 7, 7, 7, // 1101_1000 - 1101_1111
7, 7, 7, 7, 7, 7, 7, 7, // 1110_0000 - 1110_0111
7, 7, 7, 7, 7, 7, 7, 7, // 1110_1000 - 1110_1111
7, 7, 7, 7, 7, 7, 7, 7, // 1111_0000 - 1111_0111
7, 7, 7, 7, 7, 7, 7, 7, // 1111_1000 - 1111_1111
};
int byte;
int byte_cnt;
for (byte_cnt = 3; byte_cnt >= 0; byte_cnt--)
{
byte = (x >> (byte_cnt * 8)) & 0xff;
if (byte != 0)
{
return msb_lut[byte] + (byte_cnt * 8);
}
}
return -1;
}

Answer 10

Una solución ingeniosa que se me ocurrió es la búsqueda binaria de los bits.

uint64_t highestBit(uint64_t a, uint64_t bit_min, uint64_t bit_max, uint16_t bit_shift){
if(a == 0) return 0;
if(bit_min >= bit_max){
if((a & bit_min) != 0)
return bit_min;
return 0;
}
uint64_t bit_mid = bit_max >> bit_shift;
bit_shift >>= 1;
if((a >= bit_mid) && (a < (bit_mid << 1)))
return bit_mid;
else if(a > bit_mid)
return highestBit(a, bit_mid, bit_max, bit_shift);
else
return highestBit(a, bit_min, bit_mid, bit_shift);
}

Bit max es la potencia más alta de 2, por lo que para un número de 64 bits sería 2 ^ 63. El cambio de bit debe inicializarse a la mitad del número de bits, por lo que para 64 bits, sería 32.

Answer 11

como el código ofuscado? Prueba esto:

1 << (int) log2 (x)

Answer 12

fls toca una instrucción de hardware en muchas arquitecturas. Sospecho que esta es probablemente la forma más simple y rápida de hacerlo.

1<<(fls(input)-1)

Answer 13

// Note doesn''t cover the case of 0 (0 returns 1)
inline unsigned int hibit( unsigned int x )
{
unsigned int log2Val = 0 ;
while( x>>=1 ) log2Val++; // eg x=63 (111111), log2Val=5
return 1 << log2Val ; // finds 2^5=32
}