то, что мне нужно, это то, что я могу прокормить числом, и он вернет бит наивысшего порядка. Я уверен, что есть простой способ. Ниже приведен пример вывода (слева - вход)
1 -> 1 2 -> 2 3 -> 2 4 -> 4 5 -> 4 6 -> 4 7 -> 4 8 -> 8 9 -> 8 ... 63 -> 32
то, что мне нужно, это то, что я могу прокормить числом, и он вернет бит наивысшего порядка. Я уверен, что есть простой способ. Ниже приведен пример вывода (слева - вход)
1 -> 1 2 -> 2 3 -> 2 4 -> 4 5 -> 4 6 -> 4 7 -> 4 8 -> 8 9 -> 8 ... 63 -> 32
Это должно сделать трюк.
int hob (int num)
{
if (!num)
return 0;
int ret = 1;
while (num >>= 1)
ret <<= 1;
return ret;
}
hob (1234) возвращает 1024
hob (1024) возвращает 1024
hob (1023) возвращает 512
От Hacker 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);
}
Эта версия предназначена для 32-битных int, но логика может быть расширена для 64-бит или выше.
fls
заканчивается аппаратной инструкцией на многих архитектурах. Я подозреваю, что это, наверное, самый простой и быстрый способ сделать это.
1<<(fls(input)-1)
как обфускационный код? Попробуйте следующее:
1 < (int) log2 (x)
Это можно легко решить с помощью существующих вызовов библиотеки.
int highestBit(int v){
return fls(v) << 1;
}
Страница руководства Linux дает более подробную информацию об этой функции и ее сопоставлениях для других типов ввода.
Постоянно удаляйте бит младшего порядка, который приходит на ум...
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;
}
В ядре Linux есть ряд удобных битов, подобных этому, наиболее эффективный код для ряда архитектур. Вы можете найти общие версии в include/asm-generic/bitops/fls.h (и друзья), но также смотрите include/asm-x86/bitops.h для определения с использованием встроенной сборки, если скорость имеет смысл, а переносимость - нет.
Быстрый способ сделать это через справочную таблицу. Для 32-битного ввода и 8-битной таблицы поиска требуется всего 4 итерации:
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;
}
// 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
}
Немного поздно к этой вечеринке, но самое простое решение, которое я нашел, учитывая современный GCC как компилятор, просто:
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);
}
Он даже относительно портативен (по крайней мере, он будет работать на любой платформе GCC).
Если вам не требуется переносное решение, и ваш код выполняется на x86-совместимом процессоре, вы можете использовать встроенную функцию _BitScanReverse(), предоставленную компилятором Microsoft Visual C/С++. Он отображает инструкцию CPU BSR, которая возвращает самый старший бит.
Отличное решение, с которым я столкнулся, - это бинарный поиск битов.
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);
}
Бит-макс - это максимальная мощность 2, поэтому для 64-битного номера это будет 2 ^ 63. Битовый сдвиг должен быть инициализирован до половины количества бит, поэтому для 64 бит это будет 32.
Почему бы просто не сделать это:
int HiBit(int num){ return (num & 0x80000000) >> 31; }