切换MSB的最佳方法是什么?
所以我想切换我的号码中最重要的一点。 这是一个例子:
x = 100101 then answer should be 00101
我有一台64位机器因此我不希望答案是100000....100101
我想到的一种方法是计算我的数字中的位数然后切换MSB,但不确定关于如何计算。
作弊是将其典当给编译器:大多数CPU都有指令来完成这样的工作。
以下应该做你想要的。
i ^ (1 << (sizeof i * CHAR_BIT - clz(i) - 1))
这将转换为CLZ
指令,该指令计算前导零。
对于GCC,请参阅: http : //gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html
需要注意的一件事是,如果i == 0
,这会导致未定义的行为。
你应该用你的编译器的正确内在替换clz()
,在GCC中这是__builtin_clz
; 在Visual Studio C ++中,这是_BitScanForward
。
在使用GCC的情况下,@ jleahy已经发布了一个很好的选项,我只留下一个不使用任何编译器内在函数的clz
的通用实现。 但是,对于已经具有计数位的本机指令(例如x86)的CPU,它不是最佳选择。
#define __bit_msb_mask(n) (~(~0x0ul >> (n))) /* n leftmost bits. */ /* Count leading zeroes. */ int clz(unsigned long x) { int nr = 0; int sh; assert(x); /* Hope that compiler optimizes out the sizeof check. */ if (sizeof(x) == 8) { /* Suppress "shift count >= width of type" error in case * when sizeof(x) is NOT 8, ie when it is a dead code anyway. */ sh = !(x & __bit_msb_mask(sizeof(x)*8/2)) << 5; nr += sh; x <<= sh; } sh = !(x & __bit_msb_mask(1 << 4)) << 4; nr += sh; x <<= sh; sh = !(x & __bit_msb_mask(1 << 3)) << 3; nr += sh; x <<= sh; sh = !(x & __bit_msb_mask(1 << 2)) << 2; nr += sh; x <<= sh; sh = !(x & __bit_msb_mask(1 << 1)) << 1; nr += sh; x <<= sh; sh = !(x & __bit_msb_mask(1 << 0)) << 0; nr += sh; return nr; }
使用此function可以切换最重要的设置位(假设有这样一个),如下所示:
x ^= 1ul << (sizeof(x)*8 - clz(x))
这是一种使用查找表的方法,假设CHAR_BIT == 8
:
uint32_t toggle_msb(uint32_t n) { static unsigned char const lookup[] = { 1, 0, 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 7 }; for (unsigned int i = 0; i != sizeof n; ++i) { // omit the last bit for big-endian machines: ---VVVVVVVVVVVVVVVVVV unsigned char * p = reinterpret_cast(&n) + sizeof n - i - 1; if (*p / 16 != 0) { *p = *p % 16 + (lookup[*p / 16] * 16); return n; } if (*p % 16 != 0) { *p = 16 * (*p / 16) + lookup[*p % 16]; return n; } } return 1; }
并将它们放在GCC的一些示例代码中:
#include #define clz(x) __builtin_clz(x) int main() { int i = 411; /* 110011011 */ if( i != 0 ) i ^= (1 << (sizeof(i)*8 - clz(i)-1)); /* i is now 10011011 */ printf("i = %d\n", i); return(0); }