设置的最小有效位的位置

小开

有一个 x86汇编指令(bsf)可以完成. :)

更优化? ！

附注:

这个级别的优化本质上依赖于架构。今天的处理器是 太复杂了(在分支预测、缓存丢失、流水线方面) ，因此很难预测哪些代码在哪个架构上执行得更快。将操作从32减少到9之类的操作甚至可能会降低某些体系结构的性能。单个体系结构上的优化代码可能导致另一个体系结构中的代码更差。我认为你可以为特定的 CPU 优化它，或者让它保持原样，让编译器选择它认为更好的。

小开

您可以检查是否设置了任何低阶位。如果是这样，那么看看剩余位的低阶。例如:

32位 int 检查是否设置了前16位中的任何一位。如果是这样，检查是否设置了前8项中的任何一项。如果是这样..。

如果没有，检查是否有任何上16设置. 。

基本上就是二进制搜索。

小开

在最坏的情况下，只需不到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; }

小开

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; if (value & 1073741824) return 31; return 0; // no bits set }

50% 的数字会在第一行代码中返回。

75% 的数字会在前两行代码中返回。

87% 的数字会在前3行代码中返回。

94% 的数字会在代码的前4行返回。

97% 的数字会在前5行代码中返回。

等等。

想想编译器将如何把它翻译成 ASM！

对于97% 的测试用例来说，这个展开的“循环”比这个线程中发布的大多数算法都要快！

我认为那些抱怨这段代码的最坏情况是多么低效的人们并不理解这种情况会发生得多么罕见。

小开

如果你有资源，你可以牺牲内存来提高速度:

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 的表是不现实的。

小开

为什么不使用二进制搜索? 这总是在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 { ...

小开

最快的(非内部/非汇编)解决方案是找到最低字节，然后在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; }

小开

大多数现代架构都会有一些指令来查找最低设置位、最高设置位的位置，或者计算前导零的数目等等。

如果你有这个类的任何一个指令，你可以很便宜地模仿其他。

花点时间在纸上研究一下，你会发现 x & (x-1)会清除 x 中的最低设置位，而 ( x & ~(x-1) )只返回最低设置位，与结构、字长等无关。知道了这一点，如果没有明确的指令，那么使用硬件计数-前导-零/最高-集合-位来查找最低集合位是很容易的。

如果根本没有相关的硬件支持，给定给你或有点小技巧页面上的其中一个计数前导零的乘法和查找实现可以通过使用上述身份轻松地转换为给定最低集位，并且具有无分支的优点。

小开

最佳答案

Bit Twidling Hacks 提供了一个优秀的，呃，Bit Twidling 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];

有用的参考资料:

“ 使用 de Bruijn 序列在计算机文字中索引 a 1”-解释为什么上面的代码工作。

“ 主板代表 > 主板 > 主板扫描”-这个问题的详细分析，特别是国际象棋编程的重点

小开

为什么不使用内置的小费？(我从 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);

描述

Ff ()函数返回在单词 i 中设置的第一个(最小有效)位的位置。最小有效位是位置1和最大有效位，例如32或64。函数 ffsll ()和 ffsl ()执行相同的操作，但是参数的大小可能不同。

返回值

这些函数返回第一个位集的位置，如果 i 中没有设置位，则返回0。

符合

4.3 BSD，POSIX. 1-2001.

笔记

BSD 系统在 <string.h>中有一个原型。

小开

请参阅我的答案给你，了解如何使用单个 x86指令进行操作，除了要找到至少的有效集位，您需要使用 BSF(“位扫描向前”)指令而不是那里描述的 BSR。

小开

受这篇类似的文章的启发，我提供了以下内容:

unsigned GetLowestBitPos(unsigned value) { double d = value ^ (value - !!value); return (((int*)&d)[1]>>20)-1023; }

优点:

没有循环

没有分支

以恒定的时间运行

处理 value = 0，否则返回一个超出界限的结果

只有两行代码

缺点:

假设编码的 endianness 很少(可以通过更改常量来修复)

假设 double 是一个真正的 * 8 IEEE 浮点数(IEEE 754)

更新: 正如评论中指出的那样，联盟是一个更清晰的实现(至少对 C 来说) ，它看起来像是:

unsigned GetLowestBitPos(unsigned value) { union { int i[2]; double d; } temp = { .d = value ^ (value - !!value) }; return (temp.i[1] >> 20) - 1023; }

这里假设所有内容都是32位 int，并且使用 little-endian 存储(想想 x86处理器)。

小开

另一种方法(模除法和查找)值得在这里特别提到，它来自@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 */

小开

任何时候只要有一个分支，CPU 就必须猜测哪个分支将被占用。指令管道装载了指令，这些指令沿着猜测的路径引导。如果 CPU 猜错了，那么指令管道将被刷新，并且必须加载另一个分支。

考虑顶部的简单 while 循环。我们的猜测是保持在循环之内。当它离开循环时，它至少会出错一次。这将冲洗指令管。这种行为比猜测它会离开循环稍好一些，在这种情况下，它会在每次迭代中刷新指令管道。

不同类型的处理器之间丢失的 CPU 周期数量差别很大。但是你可以期待20到150个丢失的 CPU 周期。

下一个更糟糕的组是，您认为通过将值分割成更小的部分并添加更多的分支，可以节省一些迭代。这些分支中的每一个都增加了刷新指令管道的额外机会，并且花费另外20到150个时钟周期。

让我们考虑一下在表中查找值时会发生什么。有可能该值当前不在缓存中，至少在第一次调用函数时不在缓存中。这意味着，当从缓存加载值时，CPU 会停顿。同样，每台机器的情况也不同。新的 Intel 芯片实际上利用这个机会在当前线程等待缓存加载完成时交换线程。这可能比指令管道刷新开销更大，但是如果多次执行此操作，则可能只执行一次。

显然，最快的常数时间解决方案是一个涉及确定性数学。一个纯粹和优雅的解决方案。

如果已经报道过了，我很抱歉。

除了 XCODE AFAIK 之外，我使用的每个编译器都有用于正向位扫描和反向位扫描的编译器内部特性。这些将编译成一个单一的汇编指令在大多数硬件没有缓存错过，没有分支错过预测和没有其他程序员生成的绊脚石。

对于 Microsoft 编译器，请使用 _ BitScanForward & _ BitScanRT。
对于海湾合作委员会使用 _ _ 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计算，节省大量时间。

小开

下面是几种解决方案的比较基准:

我的机器是英特尔 i530(2.9 GHz) ，运行 Windows 764位。

$ 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); }

小开

根据象棋编程位扫描页面和我自己的测量，减法和 xor 比否定和掩码快。

(注意，如果要计算 0中的尾随零，方法将返回 63，而否值和掩码将返回 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];

小开

还有一个解决方案，虽然不是最快的，但看起来相当不错。
至少它没有分支。 ;)

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

小开

在“编程的艺术，第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); }

小开

最近我看到新加坡总理在 facebook 上发布了一个他写的程序，有一行提到。

逻辑就是“ value &-value”，假设您有0x0FF0，然后, 0FF0 & (F00F + 1) ，等于0x0010，这意味着最小的1位于第4位. . :)

小开

如果 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 conexpr 实现，它去掉了强制转换，并通过将一个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

小开

11年后，我们终于有了 Countr _ zero！

#include <bit> #include <bitset> #include <cstdint> #include <iostream> int main() { for (const std::uint8_t i : { 0, 0b11111111, 0b00011100, 0b00011101 }) { std::cout << "countr_zero( " << std::bitset<8>(i) << " ) = " << std::countr_zero(i) << '\n'; } }

C + + 20做得好