查找C中的最高位
我所追求的东西是我可以input一个数字，它会返回最高位。 我确定有一个简单的方法。 下面是一个输出示例（左边是input）
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; } 滚（1234）返回1024
滚（1024）返回1024
滚刀（1023）返回512
从黑客的喜悦：
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位整数，但逻辑可以扩展到64位或更高。
在许多体系结构中可以find硬件指令。 我怀疑这可能是最简单，最快速的做法。
1<<(fls(input)-1)
像混淆的代码？ 尝试这个：
1 <<（int）log2（x）
现有的库调用可以很容易地解决这个问题。
int highestBit(int v){ return fls(v) << 1; }
Linux手册页给出了关于这个函数的更多细节，以及其他inputtypes的相应细节。
不断删除低位令人想到…
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内核具有许多像这样的方便的bithop，为许多体系结构提供了最有效的编码方式。 您可以在include / asm-generic / bitops / fls.h （和朋友）中find通用版本，但是如果速度至关重要 ，可以参见include / asm-x86 / bitops.h以获得使用内联汇编的定义，而可移植性不。
一个快速的方法是通过查找表。 对于32位input和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 }
如果您不需要便携式解决scheme，并且您的代码在x86兼容CPU上执行，则可以使用Microsoft Visual C / C ++编译器提供的_BitScanReverse（）内部函数。 它映射到返回最高位设置的BSR CPU指令。
对于这个派对来说晚了一点，但是我发现最简单的解决scheme就是将现代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); }
它甚至相对便携（至less它可以在任何GCC平台上运行）。
我想出了一个漂亮的解决scheme是二进制search的位。
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; }
