我正在寻找一种有效的方法来确定以整数设置的最低有效位的位置，例如对于 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提供了一个很好的，呃，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];
有用的参考资料：
为什么不使用内置的ffs？（我从 Linux 中获取了一个手册页，但它比这更广泛。）
ffs(3) - Linux 手册页
姓名
ffs - 查找单词中设置的第一位
概要
#include <strings.h> int ffs(int i); #define _GNU_SOURCE #include <string.h> int ffsl(long int i); int ffsll(long long int i);描述
ffs() 函数返回在字 i 中设置的第一个（最低有效）位的位置。最低有效位是位置 1 和最高有效位置，例如 32 或 64。函数 ffsll() 和 ffsl() 执行相同的操作，但采用可能不同大小的参数。
返回值
这些函数返回第一个位设置的位置，如果 i 中没有设置位，则返回 0。
符合
4.3BSD，POSIX.1-2001。
笔记
BSD 系统有一个原型在
<string.h>.
有一个 x86 汇编指令 ( bsf) 可以做到这一点。:)
更优化？！
此级别的优化本质上是依赖于架构的。今天的处理器太复杂（在分支预测、缓存未命中、流水线方面），很难预测哪些代码在哪种架构上执行得更快。将操作数从 32 减少到 9 或类似的操作甚至可能会降低某些架构的性能。单一架构上的优化代码可能会导致另一个架构上的代码更差。我认为你要么针对特定的 CPU 优化它，要么保持原样，让编译器选择它认为更好的东西。
这是比较几种解决方案的基准：
我的机器是 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);
}
最快的（非内在/非汇编程序）解决方案是找到最低字节，然后在 256 条目查找表中使用该字节。这为您提供了四个条件指令的最坏情况和 1 的最佳情况。这不仅是指令数量最少，而且分支数量最少，这在现代硬件上非常重要。
您的表（256 个 8 位条目）应包含 0-255 范围内每个数字的 LSB 索引。您检查值的每个字节并找到最低的非零字节，然后使用该值查找实际索引。
这确实需要 256 字节的内存，但如果这个函数的速度如此重要，那么 256 字节就值得了，
例如
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;
}
每当你有一个分支时，CPU 必须猜测将采用哪个分支。指令管道加载了引导猜测路径的指令。如果 CPU 猜错了，则指令管道被刷新，并且必须加载另一个分支。
考虑顶部的简单 while 循环。猜测将留在循环内。当它离开循环时，它至少会出错一次。这将刷新指令管道。这种行为比猜测它会离开循环要好一些，在这种情况下，它会在每次迭代时刷新指令管道。
丢失的 CPU 周期数量因处理器类型而异。但是您可以预期会丢失 20 到 150 个 CPU 周期。
下一个更糟糕的组是您认为您将通过将值拆分为更小的部分并添加更多分支来节省一些迭代。这些分支中的每一个都增加了一个额外的机会来刷新指令管道并花费另外 20 到 150 个时钟周期。
让我们考虑一下在表中查找值时会发生什么。有可能该值当前不在缓存中，至少不是第一次调用您的函数时。这意味着在从缓存加载值时 CPU 会停止。同样，这因一台机器而异。新的英特尔芯片实际上将此作为交换线程的机会，而当前线程正在等待缓存加载完成。这很容易比指令管道刷新更昂贵，但是如果您多次执行此操作，它可能只发生一次。
显然，最快的恒定时间解决方案是涉及确定性数学的解决方案。一个纯粹而优雅的解决方案。
如果这已经被覆盖，我很抱歉。
我使用的每个编译器，除了 XCODE AFAIK，都具有用于正向位扫描和反向位扫描的编译器内在函数。这些将在大多数硬件上编译为单个汇编指令，没有缓存未命中，没有分支未命中预测，也没有其他程序员生成的绊脚石。
对于 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 或乐于为 0 获得 31，请删除 i0 计算，从而节省大量时间。
受这篇涉及搜索集合位的类似帖子的启发，我提供以下内容：
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;
}
11 年后，我们终于有了：count_zero
干得好 C++20
为什么不使用二分查找？这将始终在 5 次操作后完成（假设 int 大小为 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 { ...
在“编程艺术，第 4 部分”中使用“魔术面具”发现了这个巧妙的技巧，它在 O(log(n)) 时间内完成了 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);
}
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 行代码中返回。
等等
我认为那些抱怨这段代码的最坏情况是多么低效的人不明白这种情况会发生多么罕见。
另一种方法（模除法和查找）在@anton-tykhyy 提供的同一链接中值得特别提及。这种方法在性能上与 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 */
根据国际象棋编程 BitScan 页面和我自己的测量，减法和异或比取反和掩码更快。
（请注意，如果您要计算 中的尾随零0，则我拥有的方法返回63，而否定和掩码返回0。）
这是一个 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, 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 位版本的 negate 和 mask 方法：
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];
您可以检查是否设置了任何低位。如果是这样，请查看剩余位的低位。例如，：
32bit int - 检查是否设置了前 16 个中的任何一个。如果是这样，请检查是否设置了前 8 个中的任何一个。如果是这样的话， ....
如果没有，请检查是否设置了任何上 16 位..
本质上它是二进制搜索。
请参阅我的答案，了解如何使用单个 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
如果 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.");
这是一个简单的替代方案，尽管查找日志的成本有点高。
if(n == 0)
return 0;
return log2(n & -n)+1; //Assuming the bit index starts from 1
最近看到新加坡总理在facebook上贴了他写的一个程序，有一句话要提。。
逻辑很简单，就是“value & -value”，假设你有 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（如果我们将返回类型保留为 16 GB unsigned）。这是将一种有限资源 (RAM) 换成另一种（执行速度）的示例。
如果您的函数需要不惜一切代价保持可移植性并尽可能快地运行，那么这将是可行的方法。在大多数实际应用程序中，4GB 表是不现实的。