设置的最低有效位的位置
我正在寻找一种有效的方法来确定最低有效位的位置设置为一个整数，例如对于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提供了一个很好的收集，呃，位twiddling黑客，附加性能/优化讨论。 我最喜欢的解决方案（从该网站）是“繁复和查找”：
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序列在计算机字中索引1 ” – 解释为什么上面的代码有效。
- “ 董事会代表> Bitboards> BitScan ” – 详细分析这个问题，特别关注国际象棋程序设计
为什么不使用内置的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优化这个，要么保持原样，让编译器选择它认为更好的东西。
大多数现代的体系结构都会有一些指令来找到最低位或最高位的位置，或者计算前导零的数量等。
如果你有这门课的任何一门课程，你可以很便宜地模仿其他课程。
花一点时间在纸上写下来，并且认识到x & (x-1)将会清除x & (x-1)的最低位集，并且( x & ~(x-1) )将只返回最低的设置位，而不管体系结构，字长等等。知道这一点，如果没有明确的指令，那么使用硬件计数前导零/最高位位查找最低设置位是微不足道的。
如果根本没有相关的硬件支持，那么这里给出的count-leading- zeros或者Bit Twiddling Hacks页面上的其中一个的multiply-and-lookup实现可以被平凡地转换为使用上述标识给出最低的设置位，具有无分路的优点。
最快（非内在/非汇编）解决方案是找到最低字节，然后在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; }
Weee，大量的解决方案，而不是一个基准。 你们应该为自己感到羞耻;-)
我的机器是英特尔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从缓存中加载时，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强制为0或1，结果用于合并在分支两边发生的数学运算。
编辑：
上面的代码是完全破碎的。 此代码工作，并仍然是无分支（如果优化）：
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计算，节省大量时间。
受这个类似的帖子的启发，涉及搜索一个位，我提供以下内容：
unsigned GetLowestBitPos(unsigned value) { double d = value ^ (value - !!value); return (((int*)&d)[1]>>20)-1023; }
优点：
- 没有循环
- 没有分支
- 持续运行
- 通过返回否则超出边界的结果处理值= 0
- 只有两行代码
缺点：
- 假定编码的小尾数（可以通过改变常数来修正）
- 假定double是真实的* 8 IEEE浮点（IEEE 754）
更新：正如在注释中指出的那样，union是一个更干净的实现（至少对于C来说），如下所示：
unsigned GetLowestBitPos(unsigned value) { union { int i[2]; double d; } temp = { .d = value ^ (value - !!value) }; return (temp.i[1] >> 20) - 1023; }
这假定32位整数与小端存储的一切（认为x86处理器）。
为什么不使用二分查找 ？ 在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 { ...
这可以用少于32个操作的最坏情况来完成：
原理：检查2位或更多位与检查1位一样有效。
因此，例如，没有任何东西阻止您先检查哪个分组，然后检查该分组中的每个从最小到最大的位。
所以…
如果你在最坏的情况下（Nbits / 2）+ 1次检查总共检查2位。
如果您一次检查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; }
另一种方法（模数除法和查找）值得特别提一下@ 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];
您可以检查是否设置了任何低位。 如果是这样的话，看看剩余位的低位。 例如，：
32位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
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% of all numbers will return on the first line of code.
75% of all numbers will return on the first 2 lines of code.
87% of all numbers will return in the first 3 lines of code.
94% of all numbers will return in the first 4 lines of code.
97% of all numbers will return in the first 5 lines of code.
等等
I think people that are complaining on how inefficient the worst case scenario for this code don't understand how rare that condition will happen.
Found this clever trick using 'magic masks' in "The art of programming, part 4", which does it in O(log(n)) time for n-bit number. [with log(n) extra space]. Typical solutions checking for the set bit is either O(n) or need O(n) extra space for a look up table, so this is a good compromise.
Magic masks:
m0 = (...............01010101) m1 = (...............00110011) m2 = (...............00001111) m3 = (.......0000000011111111) ....
Key idea: No of trailing zeros in 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); }
If C++11 is available for you, a compiler sometimes can do the task for you 🙂
constexpr std::uint64_t lssb(const std::uint64_t value) { return !value ? 0 : (value % 2 ? 1 : lssb(value >> 1) + 1); }
Result is 1-based index.
This is in regards of @Anton Tykhyy answer
Here is my C++11 constexpr implementation doing away with casts and removing a warning on VC++17 by truncating a 64bit result to 32 bits:
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]; }
To get around the issue of 0x1 and 0x0 both returning 0 you can do:
constexpr uint32_t ffs ( uint32_t value ) { return (!value) ? 32 : DeBruijnSequence[ (( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF) >> 27]; }
but if the compiler can't or won't preprocess the call it will add a couple of cycles to the calculation.
Finally, if interested, here's a list of static asserts to check that the code does what is intended to:
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.");
recently I see that singapore's premier posted a program he wrote on facebook, there is one line to mention it..
The logic is simply "value & -value", suppose you have 0x0FF0, then, 0FF0 & (F00F+1) , which equals 0x0010, that means the lowest 1 is in the 4th bit.. 🙂
If you have the resources, you can sacrifice memory in order to improve the speed:
static const unsigned bitPositions[MAX_INT] = { 0, 0, 1, 0, 2, /* ... */ }; unsigned GetLowestBitPos(unsigned value) { assert(value != 0); // handled separately return bitPositions[value]; }
Note: This table would consume at least 4 GB (16 GB if we leave the return type as unsigned ). This is an example of trading one limited resource (RAM) for another (execution speed).
If your function needs to remain portable and run as fast as possible at any cost, this would be the way to go. In most real-world applications, a 4GB table is unrealistic.
