最低位的索引
我想找到获得long long最低位的索引的最快方法。 即：
00101001001000 -> 3 涉及循环和移位的解决方案太慢了。 即：
int i; if(bits == 0ULL) { i = 64; } else { for(i = 0;!(bits & 1ULL);i++) bits >>= 1; }
编辑：使用信息
使用ffsll的函数不能真正减少它的用法，但在这里（当然简化）。 它只是迭代索引并对它们做了一些事情。 这个函数可能是我整个应用程序中使用最广泛的函数，尽管有很多缓存它的价值。 它是我的alpha-beta搜索引擎中的合法移动生成器。
while(bits){ index = ffsll(bits); doSomething(index); index &= index-1; }
英特尔有专门的指令来查找最低或最高阶设置位。 BSF看起来就像你需要的那样。 至于在普通C中这样做，也许有点麻烦的黑客页面有你需要的。
至少你可以使用半字节或字节表来加快速度。 像这样的东西（为int演示，但根据需要可以很容易地改变为longlong）。
/* 0000 - 0 0001 - 1 0010 - 2 0011 - 1 0100 - 3 0101 - 1 0110 - 2 0111 - 1 1000 - 4 1001 - 1 1010 - 2 1011 - 1 1100 - 3 1101 - 1 1110 - 2 1111 - 1 */ int ffs(int i) { int ret = 0; int j = 0; static const int _ffs_tab[] = { 0, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 }; while((i != 0) && (ret == 0)) { ret = _ffs_tab[i & 0x0f]; if(ret > 0) { break; } i >>= 4; j += 4; /* technically the sign bit could stay, so we mask it out to be sure */ i &= INT_MAX; } if(ret != 0) { ret += j; } return ret; }
我发现最快的是string.h中的ffsll (long long) 。
如果使用Visual Studio， _BitScanForward ：
- http://msdn.microsoft.com/en-us/library/wfd9z0bb(VS.80).aspx(_BitScanForward）
对于gcc，请尝试__builtin_ctz或__builtin_ffs ：
与往常一样，应查阅生成的代码以确保生成正确的指令。
您可以用x & (~x + 1)隔离最低设置位; 这为您提供最低位值，而不是索引（例如，如果x = 01101000，则结果为00001000）。 我知道从那里到索引的最快方法可能是switch语句：
switch(x & (~x + 1)) { case 0ULL: index = -1; break; case 1ULL: index = 0; break; case 2ULL: index = 1; break; case 4ULL: index = 2; break; ... case 9223372036854775808ULL: index = 63; break; }
丑陋，但没有涉及循环。
如何实现一种二分搜索？
查看由比特产生的低位和掩码值，这些值都是低半部分。 如果该值为零，则您知道最小位位于数字的上半部分。
其他明智的做法将事情减半，然后再去。
这可能适用于32位。 应该很容易扩展到64。
// all bits left of lsb become 1, lsb & right become 0 y = x ^ (-x); // XOR a shifted copy recovers a single 1 in the lsb's location u = y ^ (y >> 1); // .. and isolate the bit in log2 of number of bits i0 = (u & 0xAAAAAAAA) ? 1 : 0; i1 = (u & 0xCCCCCCCC) ? 2 : 0; i2 = (u & 0xF0F0F0F0) ? 4 : 0; i3 = (u & 0xFF00FF00) ? 8 : 0; i4 = (u & 0xFFFF0000) ? 16 : 0; index = i4 | i3 | i2 | i1 | i0;
显然，如果有一些方法让硬件这样做，即，如果有特殊的CPU指令可用，那就是要走的路。
这样的事怎么样？ 它大大减少了循环次数。
int shifts = 0; if ((bits & 0xFFFFFFFFFFFFULL) == 0) // not in bottom 48 bits { shifts = 48; } else if ((bits & 0xFFFFFFFFFFULL == 0) // not in bottom 40 bits { shifts = 40; } else // etc bits >>= shifts; // do all the shifts at once // this will loop at most 8 times for(i = 0;!(bits & 1ULL);i++) bits >>= 1; index = shifts + i;
我写了两个函数，它们返回与ffsll（）相同的结果。
int func1( uint64_t n ){ if( n == 0 ) return 0; n ^= n-1; int i = 0; if( n >= 1ull<<32 ){ n>>=32; i+=32; } if( n >= 1ull<<16 ){ n>>=16; i+=16; } if( n >= 1ull<< 8 ){ n>>= 8; i+= 8; } if( n >= 1ull<< 4 ){ n>>= 4; i+= 4; } if( n >= 1ull<< 2 ){ n>>= 2; i+= 2; } if( n >= 1ull<< 1 ){ i+= 1; } return i+1; } int func2( uint64_t n ){ return n? ((union ieee754_float)((float)(n^(n-1)))).ieee.exponent-126: 0; }
我不知道哪个是最快的：ffsll（），func1（）或func2（）？
这里有两个实现，第一个是内在函数/汇编，第二个是c / c ++（索引从0开始）
unsigned int bsf_asm(unsigned int b) { // b == 0 is undefined #if defined( \__GNUC__ ) return __builtin_ctz(b); #else __asm bsf eax, b; #endif } unsigned int bsf(unsigned int b) { // b == 0 is undefined static const unsigned char btal[] = {0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0}; int i = 0; if(!(b & 0x0000ffff)) { b>>=16; i+=16; } if(!(b & 0x000000ff)) { b>>=8; i+=8; } if(!(b & 0x0000000f)) { b>>=4; i+=4; } return i+btal[b&0x0f]; }
要获得最右侧的设置位，可以使用以下表达式
将变量视为X.
x＆〜（x – 1）给出一个二进制数，它只包含设置位，其余全部为零
例
x = 0101 x-1 = 0100 ~(x-1) = 1011 x & ~ (x - 1) = 0100
现在不断地将此二进制数向右移动，直到数字为零，并计算给出最右设置位数的移位数。
如果您的数字是奇数或偶数，您可以先将算法检查的复杂性减半。 如果它是偶数，则最低位是第一个。
对于奇怪的情况，你可以实现这样的二进制搜索…