我正在寻找一种有效的方法来确定在整数中设置的最低有效位的位置，例如对于0x0FF0，它将是4。
这是一个简单的实现：
unsigned GetLowestBitPos(unsigned value)
{
assert(value != 0); // handled separately
unsigned pos = 0;
while (!(value & 1))
{
value >>= 1;
++pos;
}
return pos;
}
任何想法如何挤出一些周期？
（注意：这个问题适合喜欢这类事情的人，而不是人们告诉我xyzoptimization是邪恶的。）
[编辑]感谢大家的想法！我也学到了其他一些东西。凉！
Bit Twiddling Hacks提供了一系列精彩的，呃，有点笨拙的黑客，并附有性能/优化讨论。我最喜欢的问题解决方案（来自该网站）是«乘法和查找»：
unsigned int v; // find the number of trailing zeros in 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
有用的参考：
为什么不使用binary search？这将始终在5次操作后完成（假设int size为4个字节）：
if (0x0000FFFF & value) {
if (0x000000FF & value) {
if (0x0000000F & value) {
if (0x00000003 & value) {
if (0x00000001 & value) {
return 1;
} else {
return 2;
}
} else {
if (0x0000004 & value) {
return 3;
} else {
return 4;
}
}
} else { ...
} else { ...
} else { ...
另一种方法（模数除法和查找）值得在@ anton-tykhyy提供的相同link中特别提及。这种方法在性能上与DeBruijn乘法和查找方法非常相似，只有轻微但重要的区别。
模数除法和查找
unsigned int v; // find the number of trailing zeros in v
int r; // put the result in r
static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
{
32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
20, 8, 19, 18
};
r = Mod37BitPosition[(-v & v) % 37];
模数除法和查找方法为v = 0x00000000和v = FFFFFFFF返回不同的值，而DeBruijn乘法和查找方法在两个输入上返回零。
测试：-
unsigned int n1=0x00000000, n2=0xFFFFFFFF;
MultiplyDeBruijnBitPosition[((unsigned int )((n1 & -n1) * 0x077CB531U)) >> 27]); /* returns 0 */
MultiplyDeBruijnBitPosition[((unsigned int )((n2 & -n2) * 0x077CB531U)) >> 27]); /* returns 0 */
Mod37BitPosition[(((-(n1) & (n1))) % 37)]); /* returns 32 */
Mod37BitPosition[(((-(n2) & (n2))) % 37)]); /* returns 0 */
根据Chess Programming BitScan page和我自己的测量，减法和xor比否定和掩盖更快。
（注意，如果你要计算0中的尾随零，我的方法返回63而negate和mask返回0。）
这是一个64位减法和xor：
unsigned long v; // find the number of trailing zeros in 64-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[64] =
{
0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61,
54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62,
46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v ^ (v-1)) * 0x03F79D71B4CB0A89U)) >> 58];
作为参考，这是一个64位版本的否定和掩码方法：
unsigned long v; // find the number of trailing zeros in 64-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[64] =
{
0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4,
62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5,
63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11,
46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x03F79D71B4CB0A89U)) >> 58];
您可以检查是否设置了任何低位。如果是，则查看剩余位的低位。例如。，：
32位int - 检查是否设置了前16个中的任何一个。如果是，请检查是否设置了前8个中的任何一个。如果是这样， ....
如果没有，检查是否有任何上面的16 ..
基本上它是二进制搜索。
请参阅我的答案here，了解如何使用单个x86指令执行此操作，除了找到最低有效设置位，您需要BSF（“位扫描前进”）指令而不是那里描述的BSR。
还有另一种解决方案，可能不是最快的，但似乎相当不错。 至少它没有分支。 ;）
uint32 x = ...; // 0x00000001 0x0405a0c0 0x00602000
x |= x << 1; // 0x00000003 0x0c0fe1c0 0x00e06000
x |= x << 2; // 0x0000000f 0x3c3fe7c0 0x03e1e000
x |= x << 4; // 0x000000ff 0xffffffc0 0x3fffe000
x |= x << 8; // 0x0000ffff 0xffffffc0 0xffffe000
x |= x << 16; // 0xffffffff 0xffffffc0 0xffffe000
// now x is filled with '1' from the least significant '1' to bit 31
x = ~x; // 0x00000000 0x0000003f 0x00001fff
// now we have 1's below the original least significant 1
// let's count them
x = x & 0x55555555 + (x >> 1) & 0x55555555;
// 0x00000000 0x0000002a 0x00001aaa
x = x & 0x33333333 + (x >> 2) & 0x33333333;
// 0x00000000 0x00000024 0x00001444
x = x & 0x0f0f0f0f + (x >> 4) & 0x0f0f0f0f;
// 0x00000000 0x00000006 0x00000508
x = x & 0x00ff00ff + (x >> 8) & 0x00ff00ff;
// 0x00000000 0x00000006 0x0000000d
x = x & 0x0000ffff + (x >> 16) & 0x0000ffff;
// 0x00000000 0x00000006 0x0000000d
// least sign.bit pos. was: 0 6 13
unsigned GetLowestBitPos(unsigned value)
{
if (value & 1) return 1;
if (value & 2) return 2;
if (value & 4) return 3;
if (value & 8) return 4;
if (value & 16) return 5;
if (value & 32) return 6;
if (value & 64) return 7;
if (value & 128) return 8;
if (value & 256) return 9;
if (value & 512) return 10;
if (value & 1024) return 11;
if (value & 2048) return 12;
if (value & 4096) return 13;
if (value & 8192) return 14;
if (value & 16384) return 15;
if (value & 32768) return 16;
if (value & 65536) return 17;
if (value & 131072) return 18;
if (value & 262144) return 19;
if (value & 524288) return 20;
if (value & 1048576) return 21;
if (value & 2097152) return 22;
if (value & 4194304) return 23;
if (value & 8388608) return 24;
if (value & 16777216) return 25;
if (value & 33554432) return 26;
if (value & 67108864) return 27;
if (value & 134217728) return 28;
if (value & 268435456) return 29;
if (value & 536870912) return 30;
return 31;
}
所有数字的50％将返回第一行代码。
所有数字的75％将在前2行代码中返回。
所有数字的87％将在前3行代码中返回。
所有数字的94％将在前4行代码中返回。
所有数字的97％将在前5行代码中返回。
等等
我认为那些抱怨这个代码的最坏情况如何效率低下的人不理解这种情况会发生多么罕见。
在“编程的艺术，第4部分”中使用“魔术掩模”找到了这个聪明的技巧，它在n位数的O（log（n））时间内完成。 [与log（n）额外空间]。检查设置位的典型解决方案是O（n）或需要O（n）额外空间用于查找表，因此这是一个很好的折衷方案。
魔术面具：
m0 = (...............01010101)
m1 = (...............00110011)
m2 = (...............00001111)
m3 = (.......0000000011111111)
....
关键思想：在x = 1 * [（x＆m0）= 0] + 2 * [（x＆m1）= 0] + 4 * [（x＆m2）= 0] + ...中没有尾随零
int lastSetBitPos(const uint64_t x) {
if (x == 0) return -1;
//For 64 bit number, log2(64)-1, ie; 5 masks needed
int steps = log2(sizeof(x) * 8); assert(steps == 6);
//magic masks
uint64_t m[] = { 0x5555555555555555, // .... 010101
0x3333333333333333, // .....110011
0x0f0f0f0f0f0f0f0f, // ...00001111
0x00ff00ff00ff00ff, //0000000011111111
0x0000ffff0000ffff,
0x00000000ffffffff };
//Firstly extract only the last set bit
uint64_t y = x & -x;
int trailZeros = 0, i = 0 , factor = 0;
while (i < steps) {
factor = ((y & m[i]) == 0 ) ? 1 : 0;
trailZeros += factor * pow(2,i);
++i;
}
return (trailZeros+1);
}
如果C ++ 11可供您使用，编译器有时可以为您完成任务:)
constexpr std::uint64_t lssb(const std::uint64_t value)
{
return !value ? 0 : (value % 2 ? 1 : lssb(value >> 1) + 1);
}
结果是从1开始的索引。
这是关于@Anton Tykhyy的回答
这是我的C ++ 11 constexpr实现通过将64位结果截断为32位来消除强制转换并删除VC ++ 17上的警告：
constexpr uint32_t DeBruijnSequence[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
constexpr uint32_t ffs ( uint32_t value )
{
return DeBruijnSequence[
(( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
>> 27];
}
要解决0x1和0x0都返回0的问题，你可以这样做：
constexpr uint32_t ffs ( uint32_t value )
{
return (!value) ? 32 : DeBruijnSequence[
(( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
>> 27];
}
但如果编译器不能或不会预处理调用，它将为计算添加几个周期。
最后，如果感兴趣，这里是一个静态断言列表，用于检查代码是否符合以下目的：
static_assert (ffs(0x1) == 0, "Find First Bit Set Failure.");
static_assert (ffs(0x2) == 1, "Find First Bit Set Failure.");
static_assert (ffs(0x4) == 2, "Find First Bit Set Failure.");
static_assert (ffs(0x8) == 3, "Find First Bit Set Failure.");
static_assert (ffs(0x10) == 4, "Find First Bit Set Failure.");
static_assert (ffs(0x20) == 5, "Find First Bit Set Failure.");
static_assert (ffs(0x40) == 6, "Find First Bit Set Failure.");
static_assert (ffs(0x80) == 7, "Find First Bit Set Failure.");
static_assert (ffs(0x100) == 8, "Find First Bit Set Failure.");
static_assert (ffs(0x200) == 9, "Find First Bit Set Failure.");
static_assert (ffs(0x400) == 10, "Find First Bit Set Failure.");
static_assert (ffs(0x800) == 11, "Find First Bit Set Failure.");
static_assert (ffs(0x1000) == 12, "Find First Bit Set Failure.");
static_assert (ffs(0x2000) == 13, "Find First Bit Set Failure.");
static_assert (ffs(0x4000) == 14, "Find First Bit Set Failure.");
static_assert (ffs(0x8000) == 15, "Find First Bit Set Failure.");
static_assert (ffs(0x10000) == 16, "Find First Bit Set Failure.");
static_assert (ffs(0x20000) == 17, "Find First Bit Set Failure.");
static_assert (ffs(0x40000) == 18, "Find First Bit Set Failure.");
static_assert (ffs(0x80000) == 19, "Find First Bit Set Failure.");
static_assert (ffs(0x100000) == 20, "Find First Bit Set Failure.");
static_assert (ffs(0x200000) == 21, "Find First Bit Set Failure.");
static_assert (ffs(0x400000) == 22, "Find First Bit Set Failure.");
static_assert (ffs(0x800000) == 23, "Find First Bit Set Failure.");
static_assert (ffs(0x1000000) == 24, "Find First Bit Set Failure.");
static_assert (ffs(0x2000000) == 25, "Find First Bit Set Failure.");
static_assert (ffs(0x4000000) == 26, "Find First Bit Set Failure.");
static_assert (ffs(0x8000000) == 27, "Find First Bit Set Failure.");
static_assert (ffs(0x10000000) == 28, "Find First Bit Set Failure.");
static_assert (ffs(0x20000000) == 29, "Find First Bit Set Failure.");
static_assert (ffs(0x40000000) == 30, "Find First Bit Set Failure.");
static_assert (ffs(0x80000000) == 31, "Find First Bit Set Failure.");
为什么不使用内置的ffs？ （我从Linux手中获取了一个手册页，但它比这更广泛。）
ffs（3） - Linux手册页
Name
ffs - 查找单词中的第一个位
Synopsis
#include <strings.h> int ffs(int i); #define _GNU_SOURCE #include <string.h> int ffsl(long int i); int ffsll(long long int i);Description
ffs（）函数返回单词i中设置的第一个（最低有效）位的位置。最低有效位是位置1和最重要的位置，例如函数ffsll（）和ffsl（）执行相同的操作但接受可能不同大小的参数。
Return Value
这些函数返回第一个位集的位置，如果i中没有设置位，则返回0。
Conforming to
4.3BSD，POSIX.1-2001。
Notes
BSD系统在
<string.h>中有一个原型。
这是一个简单的替代方案，即使找到日志有点贵。
if(n == 0)
return 0;
return log2(n & -n)+1; //Assuming the bit index starts from 1
最近我看到新加坡总理发布了他在facebook上写的一个程序，有一行提到它。
逻辑只是“值＆ - 值”，假设你有0x0FF0，那么，0FF0＆（F00F + 1），等于0x0010，这意味着最低1位于第4位.. :)
如果你有资源，你可以牺牲内存以提高速度：
static const unsigned bitPositions[MAX_INT] = { 0, 0, 1, 0, 2, /* ... */ };
unsigned GetLowestBitPos(unsigned value)
{
assert(value != 0); // handled separately
return bitPositions[value];
}
注意：此表将消耗至少4 GB（如果我们将返回类型保留为unsigned，则为16 GB）。这是将一个有限资源（RAM）换成另一个（执行速度）的示例。
如果你的功能需要保持便携并且不惜一切代价尽快运行，那么这就是你要走的路。在大多数实际应用中，4GB表是不现实的。
有一个x86汇编指令（bsf）可以做到这一点。 :)
更优化？！
此级别的优化本质上取决于架构。今天的处理器过于复杂（在分支预测，缓存未命中，流水线方面），很难预测哪个代码在哪个架构上执行得更快。将操作从32减少到9或类似的事情甚至可能会降低某些体系结构的性能。单个体系结构上的优化代码可能会导致另一个体系结构中的代码更糟糕。我想你要么为特定的CPU优化它，要么保持原样，让编译器选择它认为更好的东西。
大多数现代架构都会有一些指令来查找最低设置位的位置，或最高设置位，或计算前导零的数量等。
如果你有这个课程的任何一个指令，你可以便宜地模仿其他人。
花一点时间在纸上完成它并意识到x & (x-1)将清除x中的最低设置位，并且( x & ~(x-1) )将返回最低设置位，而不管结构，字长等。知道这一点，使用硬件计数是微不足道的-leading-zero /最高设置位，如果没有明确的指令，则找到最低设置位。
如果根本没有相关的硬件支持，给定here或Bit Twiddling Hacks页面上的其中一个的count-leading-zero的乘法和查找实现可以使用上述标识简单地转换为给出最低设置位并具有无分支的优势。
最快（非内在/非汇编）解决方案是找到最低字节，然后在256条目查找表中使用该字节。这给出了四个条件指令的最坏情况性能和最佳情况1.这不仅是指令数量最少，而且是现代硬件上最重要的分支数量。
您的表（256个8位条目）应包含0-255范围内每个数字的LSB索引。检查值的每个字节并找到最低的非零字节，然后使用此值查找实际索引。
这确实需要256字节的内存，但如果这个函数的速度如此重要，那么256字节非常值得，
EG
byte lowestBitTable[256] = {
.... // left as an exercise for the reader to generate
};
unsigned GetLowestBitPos(unsigned value)
{
// note that order to check indices will depend whether you are on a big
// or little endian machine. This is for little-endian
byte* bytes = (byte*)value;
if (bytes[0])
return lowestBitTable[bytes[0]];
else if (bytes[1])
return lowestBitTable[bytes[1]] + 8;
else if (bytes[2])
return lowestBitTable[bytes[2]] + 16;
else
return lowestBitTable[bytes[3]] + 24;
}
Weee，大量的解决方案，而不是一个基准。你们应该为自己感到羞耻;-)
我的机器是Intel i530（2.9 GHz），运行Windows 7 64位。我用32位版本的MinGW编译。
$ gcc --version
gcc.exe (GCC) 4.7.2
$ gcc bench.c -o bench.exe -std=c99 -Wall -O2
$ bench
Naive loop. Time = 2.91 (Original questioner)
De Bruijn multiply. Time = 1.16 (Tykhyy)
Lookup table. Time = 0.36 (Andrew Grant)
FFS instruction. Time = 0.90 (ephemient)
Branch free mask. Time = 3.48 (Dan / Jim Balter)
Double hack. Time = 3.41 (DocMax)
$ gcc bench.c -o bench.exe -std=c99 -Wall -O2 -march=native
$ bench
Naive loop. Time = 2.92
De Bruijn multiply. Time = 0.47
Lookup table. Time = 0.35
FFS instruction. Time = 0.68
Branch free mask. Time = 3.49
Double hack. Time = 0.92
我的代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY_SIZE 65536
#define NUM_ITERS 5000 // Number of times to process array
int find_first_bits_naive_loop(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
if (value == 0)
continue;
unsigned pos = 0;
while (!(value & 1))
{
value >>= 1;
++pos;
}
total += pos + 1;
}
}
return total;
}
int find_first_bits_de_bruijn(unsigned nums[ARRAY_SIZE])
{
static const int MultiplyDeBruijnBitPosition[32] =
{
1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9,
32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
};
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned int c = nums[i];
total += MultiplyDeBruijnBitPosition[((unsigned)((c & -c) * 0x077CB531U)) >> 27];
}
}
return total;
}
unsigned char lowestBitTable[256];
int get_lowest_set_bit(unsigned num) {
unsigned mask = 1;
for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) {
if (num & mask) {
return cnt;
}
}
return 0;
}
int find_first_bits_lookup_table(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned int value = nums[i];
// note that order to check indices will depend whether you are on a big
// or little endian machine. This is for little-endian
unsigned char *bytes = (unsigned char *)&value;
if (bytes[0])
total += lowestBitTable[bytes[0]];
else if (bytes[1])
total += lowestBitTable[bytes[1]] + 8;
else if (bytes[2])
total += lowestBitTable[bytes[2]] + 16;
else
total += lowestBitTable[bytes[3]] + 24;
}
}
return total;
}
int find_first_bits_ffs_instruction(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
total += __builtin_ffs(nums[i]);
}
}
return total;
}
int find_first_bits_branch_free_mask(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
int i16 = !(value & 0xffff) << 4;
value >>= i16;
int i8 = !(value & 0xff) << 3;
value >>= i8;
int i4 = !(value & 0xf) << 2;
value >>= i4;
int i2 = !(value & 0x3) << 1;
value >>= i2;
int i1 = !(value & 0x1);
int i0 = (value >> i1) & 1? 0 : -32;
total += i16 + i8 + i4 + i2 + i1 + i0 + 1;
}
}
return total;
}
int find_first_bits_double_hack(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
double d = value ^ (value - !!value);
total += (((int*)&d)[1]>>20)-1022;
}
}
return total;
}
int main() {
unsigned nums[ARRAY_SIZE];
for (int i = 0; i < ARRAY_SIZE; i++) {
nums[i] = rand() + (rand() << 15);
}
for (int i = 0; i < 256; i++) {
lowestBitTable[i] = get_lowest_set_bit(i);
}
clock_t start_time, end_time;
int result;
start_time = clock();
result = find_first_bits_naive_loop(nums);
end_time = clock();
printf("Naive loop. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_de_bruijn(nums);
end_time = clock();
printf("De Bruijn multiply. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_lookup_table(nums);
end_time = clock();
printf("Lookup table. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_ffs_instruction(nums);
end_time = clock();
printf("FFS instruction. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_branch_free_mask(nums);
end_time = clock();
printf("Branch free mask. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_double_hack(nums);
end_time = clock();
printf("Double hack. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
}
OMG只是螺旋式上升。
大多数这些例子缺乏的是对所有硬件如何工作的一点了解。
只要你有一个分支，CPU就必须猜测将采取哪个分支。指令管道加载了引导猜测路径的指令。如果CPU猜错了，则刷新指令管道，并且必须加载另一个分支。
考虑顶部的简单while循环。猜测将保持在循环内。它离开循环时至少会出错一次。这将刷新指令管道。这种行为稍微好于猜测它会离开循环，在这种情况下它会在每次迭代时刷新指令管道。
从一种处理器到下一种处理器，丢失的CPU周期量变化很大。但是你可以预期20到150个CPU周期丢失。
下一个更糟糕的组是您认为通过将值拆分为更小的块并添加更多分支来保存几次迭代的位置。这些分支中的每一个都增加了冲洗指令管道的额外机会，并且花费另外20到150个时钟周期。
让我们考虑一下在表中查找值时会发生什么。有可能当前值不在缓存中，至少不是第一次调用函数。这意味着在从缓存加载值时CPU将停止运行。同样，这也因机器而异。新的英特尔芯片实际上使用它作为交换线程的机会，而当前线程正在等待缓存加载完成。这可能比指令管道刷新更加昂贵，但是如果您多次执行此操作，则可能只发生一次。
显然，最快的恒定时间解决方案是涉及确定性数学的解决方案。一个纯粹而优雅的解决方案
如果这已经被覆盖，我表示歉意。
我使用的每个编译器（XCODE AFAIK除外）都具有前向位扫描和反向位扫描的编译器内在函数。这些将在大多数硬件上编译为单个汇编指令，没有Cache Miss，没有Branch Miss-Prediction，也没有其他程序员生成绊脚石块。
对于Microsoft编译器，请使用_BitScanForward和_BitScanReverse。 对于GCC，请使用__builtin_ffs，__ builtin_clz，__ builtin_ctz。
此外，如果您对所讨论的主题知之甚少，请不要发布答案并可能误导新人。
对不起，我完全忘了提供解决方案..这是我在IPAD上使用的代码，它没有任务的汇编级指令：
unsigned BitScanLow_BranchFree(unsigned value)
{
bool bwl = (value & 0x0000ffff) == 0;
unsigned I1 = (bwl * 15);
value = (value >> I1) & 0x0000ffff;
bool bbl = (value & 0x00ff00ff) == 0;
unsigned I2 = (bbl * 7);
value = (value >> I2) & 0x00ff00ff;
bool bnl = (value & 0x0f0f0f0f) == 0;
unsigned I3 = (bnl * 3);
value = (value >> I3) & 0x0f0f0f0f;
bool bsl = (value & 0x33333333) == 0;
unsigned I4 = (bsl * 1);
value = (value >> I4) & 0x33333333;
unsigned result = value + I1 + I2 + I3 + I4 - 1;
return result;
}
这里需要理解的是，这不是比较昂贵的，而是比较后发生的分支。在这种情况下的比较强制为值为0或1，而.. == 0，结果用于组合分支两侧可能发生的数学运算。
编辑：
上面的代码完全破碎了。此代码有效并且仍然是无分支的（如果已优化）：
int BitScanLow_BranchFree(ui value)
{
int i16 = !(value & 0xffff) << 4;
value >>= i16;
int i8 = !(value & 0xff) << 3;
value >>= i8;
int i4 = !(value & 0xf) << 2;
value >>= i4;
int i2 = !(value & 0x3) << 1;
value >>= i2;
int i1 = !(value & 0x1);
int i0 = (value >> i1) & 1? 0 : -32;
return i16 + i8 + i4 + i2 + i1 + i0;
}
如果给定为0，则返回-1。如果您不关心0或者很高兴得到31为0，则删除i0计算，节省一大块时间。
受this similar post的启发，涉及搜索一下，我提供以下内容：
unsigned GetLowestBitPos(unsigned value)
{
double d = value ^ (value - !!value);
return (((int*)&d)[1]>>20)-1023;
}
优点：
缺点：
更新：正如评论中所指出的，联盟是一个更清晰的实现（对于C，至少），看起来像：
unsigned GetLowestBitPos(unsigned value)
{
union {
int i[2];
double d;
} temp = { .d = value ^ (value - !!value) };
return (temp.i[1] >> 20) - 1023;
}
假设32位整数用于所有内容的小端存储（想想x86处理器）。
它可以在少于32次操作的最坏情况下完成：
原理：检查2位或更多位与检查1位一样有效。
因此，例如，没有什么可以阻止您首先检查其分组，然后检查该组中从最小到最大的每个位。
所以... 如果你在最坏的情况下检查2位（Nbits / 2）+ 1总检查。 如果你一次检查3位，你在最坏的情况下（Nbits / 3）+ 2检查总数。 ...
最佳的是检查4组。在最坏的情况下，需要11个操作而不是32个操作。
最好的情况是从算法的1检查到2检查，如果你使用这种分组的想法。但是最好的情况下额外的1次检查对于最坏的情况节省是值得的。
注意：我完全写出来而不是使用循环，因为它更有效。
int getLowestBitPos(unsigned int value)
{
//Group 1: Bits 0-3
if(value&0xf)
{
if(value&0x1)
return 0;
else if(value&0x2)
return 1;
else if(value&0x4)
return 2;
else
return 3;
}
//Group 2: Bits 4-7
if(value&0xf0)
{
if(value&0x10)
return 4;
else if(value&0x20)
return 5;
else if(value&0x40)
return 6;
else
return 7;
}
//Group 3: Bits 8-11
if(value&0xf00)
{
if(value&0x100)
return 8;
else if(value&0x200)
return 9;
else if(value&0x400)
return 10;
else
return 11;
}
//Group 4: Bits 12-15
if(value&0xf000)
{
if(value&0x1000)
return 12;
else if(value&0x2000)
return 13;
else if(value&0x4000)
return 14;
else
return 15;
}
//Group 5: Bits 16-19
if(value&0xf0000)
{
if(value&0x10000)
return 16;
else if(value&0x20000)
return 17;
else if(value&0x40000)
return 18;
else
return 19;
}
//Group 6: Bits 20-23
if(value&0xf00000)
{
if(value&0x100000)
return 20;
else if(value&0x200000)
return 21;
else if(value&0x400000)
return 22;
else
return 23;
}
//Group 7: Bits 24-27
if(value&0xf000000)
{
if(value&0x1000000)
return 24;
else if(value&0x2000000)
return 25;
else if(value&0x4000000)
return 26;
else
return 27;
}
//Group 8: Bits 28-31
if(value&0xf0000000)
{
if(value&0x10000000)
return 28;
else if(value&0x20000000)
return 29;
else if(value&0x40000000)
return 30;
else
return 31;
}
return -1;
}