programacion - Encuentra el bit de orden más alto en C
bit type c (13)
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
¿Por qué no simplemente hacer esto?
int HiBit(int num){ return (num & 0x80000000) >> 31; }
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;
}
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.
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.
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
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.
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.
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).
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;
}
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.
como el código ofuscado? Prueba esto:
1 << (int) log2 (x)
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)
// 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
}