如何使用位操作有效地find64位值中唯一位的位置？
只要说我有一个值typesuint64_t看作八位字节序列（1八位字节= 8位）。 已知uint64_t值只包含MSB位置上的一个设定位 。 因此， uint64_t值可以是下列二进制表示之一：
00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 pos = 7 00000000 00000000 00000000 00000000 00000000 00000000 10000000 00000000 pos = 15 00000000 00000000 00000000 00000000 00000000 10000000 00000000 00000000 pos = 23 00000000 00000000 00000000 00000000 10000000 00000000 00000000 00000000 pos = 31 00000000 00000000 00000000 10000000 00000000 00000000 00000000 00000000 pos = 39 00000000 00000000 10000000 00000000 00000000 00000000 00000000 00000000 pos = 47 00000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000 pos = 55 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 pos = 63
我需要一个快速函数返回设置位的位置，但如果没有设置位返回0。
如果可能的话，我希望它没有循环也不分支。
将该值乘以精心devise的64位常数，然后屏蔽掉高4位。 对于任何具有快速64位乘法的CPU，这可能是最佳的，因为你可以得到。
int field_set(uint64_t input) { uint64_t field = input * 0x20406080a0c0e1ULL; return (field >> 60) & 15; } // field_set(0x0000000000000000ULL) = 0 // field_set(0x0000000000000080ULL) = 1 // field_set(0x0000000000008000ULL) = 2 // field_set(0x0000000000800000ULL) = 3 // field_set(0x0000000080000000ULL) = 4 // field_set(0x0000008000000000ULL) = 5 // field_set(0x0000800000000000ULL) = 6 // field_set(0x0080000000000000ULL) = 7 // field_set(0x8000000000000000ULL) = 8
铛实现这三个x86_64指令，不包括框架设置和清理：
_field_set: push %rbp mov %rsp,%rbp movabs $0x20406080a0c0e1,%rax imul %rdi,%rax shr $0x3c,%rax pop %rbp retq
请注意，任何其他input的结果将非常随机。 （所以不要这样做。）
我不认为有任何可行的方法来扩展此方法直接返回值在7..63范围内（该常数的结构不允许它），但您可以转换结果乘以结果由7。
关于这个常数是如何devise的：我从以下观察开始：
- 无符号乘法是大多数CPU上的快速操作，并且可以产生有用的效果。 我们应该使用它。 🙂
- 用零乘以任何东西都会导致零。 由于这与无比特集合input的期望结果相匹配，所以我们目前做得很好。
- 通过
1ULL<<63（即，你的“pos = 63”值）乘以任何东西只可能导致相同的值或零。 （它不可能有任何低位设置，也没有高位可以改变。）因此，我们必须find一些方法来将这个值作为正确的结果。 - 将这个值作为自己的正确结果的一个方便的方法是将其右移60位。 这转移到“8”，这是一个足够方便的表示。 我们可以继续将其他输出编码为1到7。
-
将我们的常数乘以其他位域的每一个等于将它左移到与其“位置”相等的位数。 右移60位只会使得给定位置左边的4位出现在结果中。 因此，我们可以创build除以下所有情况之外的所有情况：
uint64_t constant = ( 1ULL << (60 - 7) | 2ULL << (60 - 15) | 3ULL << (60 - 23) | 4ULL << (60 - 31) | 5ULL << (60 - 39) | 6ULL << (60 - 47) | 7ULL << (60 - 55) );
到目前为止，常量是0x20406080a0c0e0ULL 。 但是，这并不能给出pos=63的正确结果。 这个常数是偶数，所以把它乘以那个input就是零。 我们必须设置最低位（即， constant |= 1ULL ）来使该情况起作用，给我们最终的值0x20406080a0c0e1ULL 。
请注意，上面的构造可以修改，以不同的方式编码结果。 然而， 8的输出如上所述是固定的，而所有其他输出必须适合4位（即0到15）。
这是一个便携式解决scheme，然而，这比使用clz （计数前导零）等专用指令的解决scheme要慢。 我在algorithm的每一步添加了注释，解释了它是如何工作的。
#include <stdio.h> #include <stdlib.h> #include <stdint.h> /* return position of set bit, if exactly one of bits n*8-1 is set; n in [1,8] return 0 if no bit is set */ int bit_pos (uint64_t a) { uint64_t t, c; t = a - 1; // create mask c = t >> 63; // correction for zero inputs t = t + c; // apply zero correction if necessary t = t & 0x0101010101010101ULL; // mark each byte covered by mask t = t * 0x0101010101010101ULL; // sum the byte markers in uppermost byte t = (t >> 53) - 1; // retrieve count and diminish by 1 for bit position t = t + c; // apply zero correction if necessary return (int)t; } int main (void) { int i; uint64_t a; a = 0; printf ("a=%016llx bit_pos=%2d reference_pos=%2d\n", a, bit_pos(a), 0); for (i = 7; i < 64; i += 8) { a = (1ULL << i); printf ("a=%016llx bit_pos=%2d reference_pos=%2d\n", a, bit_pos(a), i); } return EXIT_SUCCESS; }
这段代码的输出应该如下所示：
a=0000000000000000 bit_pos= 0 reference_pos= 0 a=0000000000000080 bit_pos= 7 reference_pos= 7 a=0000000000008000 bit_pos=15 reference_pos=15 a=0000000000800000 bit_pos=23 reference_pos=23 a=0000000080000000 bit_pos=31 reference_pos=31 a=0000008000000000 bit_pos=39 reference_pos=39 a=0000800000000000 bit_pos=47 reference_pos=47 a=0080000000000000 bit_pos=55 reference_pos=55 a=8000000000000000 bit_pos=63 reference_pos=63
在x86_64平台上，我的编译器将bit_pos()转换成这个机器码：
bit_pos PROC lea r8, QWORD PTR [-1+rcx] shr r8, 63 mov r9, 0101010101010101H lea rdx, QWORD PTR [-1+r8+rcx] and rdx, r9 imul r9, rdx shr r9, 53 lea rax, QWORD PTR [-1+r8+r9] ret
[稍后更新]
黄昏时的回答使我清楚，我原来的想法是不必要的错综复杂的。 事实上，使用duskwuff的方法，所需的function可以更简洁地expression如下：
/* return position of set bit, if exactly one of bits n*8-1 is set; n in [1,8] return 0 if no bit is set */ int bit_pos (uint64_t a) { const uint64_t magic_multiplier = (( 7ULL << 56) | (15ULL << 48) | (23ULL << 40) | (31ULL << 32) | (39ULL << 24) | (47ULL << 16) | (55ULL << 8) | (63ULL << 0)); return (int)(((a >> 7) * magic_multiplier) >> 56); }
任何合理的编译器都会预先计算出魔法乘数，即0x070f171f272f373fULL 。 为x86_64目标发出的代码收缩
bit_pos PROC mov rax, 070f171f272f373fH shr rcx, 7 imul rax, rcx shr rax, 56 ret
如果你可以使用POSIX，使用strings.h （不是string.h ！）中的ffs()函数。 它返回最低有效位集合（一个索引）的位置，如果参数为零，则返回一个零。 在大多数实现中，调用ffs()被内联并编译到相应的机器指令中，如x86上的bsf 。 glibc也有ffsll() long long参数，如果可用的话，它应该更适合你的问题。
值mod 0x8C为每种情况产生一个唯一的值。
这个值0x11仍然是唯一的。
表中的第二个值是结果mod 0x11。
128 9 32768 5 8388608 10 2147483648 0 549755813888 14 140737488355328 2 36028797018963968 4 9223372036854775808 15
所以一个简单的查找表就足够了。
int find_bit(uint64_t bit){ int lookup[] = { the seventeen values }; return lookup[ (bit % 0x8C) % 0x11]; }
没有分支，没有编译器的技巧。
为了完整性，数组是
{ 31, 0, 47, 15, 55, 0, 0, 7, 23, 0, 0, 0, 39, 63, 0, 0}
如果你想要一个algorithm而不是一个内置的工作，这将做到这一点。 即使设置了多个位，它也会产生最重要的1位的位数。 它通过将所考虑的比特范围迭代地分成两半来缩小位置，testing在上半部分中是否设置了任何比特，如果是，则将该半部分作为新比特范围，否则将下半部分作为新比特范围。
#define TRY_WINDOW(bits, n, msb) do { \ uint64_t t = n >> bits; \ if (t) { \ msb += bits; \ n = t; \ } \ } while (0) int msb(uint64_t n) { int msb = 0; TRY_WINDOW(32, n, msb); TRY_WINDOW(16, n, msb); TRY_WINDOW( 8, n, msb); TRY_WINDOW( 4, n, msb); TRY_WINDOW( 2, n, msb); TRY_WINDOW( 1, n, msb); return msb; }
C ++标记被删除了，但是这里是一个可移植的C ++答案，因为你可以用C ++编译它，并使用一个extern C接口：
如果你有一个2的幂，你减去一个，你会得到一个二进制数字，设置的位数等于该位置
在std::bitset成员函数count设置位数（二进制1 s）的方法大概是最有效的，每次执行stl
请注意，您的规范已0返回0或1 ，所以我添加as_specified_pos以满足此要求。 就个人而言，我会把它返回到64时的自然值为0来区分，并且为了速度。
下面的代码应该是非常便携的，并且很可能被编译器供应商按平台优化：
#include <bitset> uint64_t pos(uint64_t val) { return std::bitset<64>(val-1).count(); } uint64_t as_specified_pos(uint64_t val) { return (val) ? pos(val) : 0; }
在使用g ++的Linux上，我得到以下反汇编代码：
0000000000000000 <pos(unsigned long)>: 0: 48 8d 47 ff lea -0x1(%rdi),%rax 4: f3 48 0f b8 c0 popcnt %rax,%rax 9: c3 retq a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1) 0000000000000010 <as_specified_pos(unsigned long)>: 10: 31 c0 xor %eax,%eax 12: 48 85 ff test %rdi,%rdi 15: 74 09 je 20 <as_specified_pos(unsigned long)+0x10> 17: 48 8d 47 ff lea -0x1(%rdi),%rax 1b: f3 48 0f b8 c0 popcnt %rax,%rax 20: f3 c3 repz retq
现代硬件有专门的指令（英特尔处理器上的LZCNT，TZCNT）。
大多数编译器都有内build函数来轻松生成它们。 请参阅以下维基百科页面 。
00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 pos = 7…，但如果没有设置位，则返回0。
如果第一位或者没有位被设置，这将返回相同的; 不过，在x86_64上，这正是bsrq所做的：
int bsrq_x86_64(uint64_t x){ int ret; asm("bsrq %0, %1":"=r"(ret):"r"(x)); return ret; }
然而; 如果第一位被设置，它也将返回0; 这里是一个运行在恒定时间（无循环或分支）的方法，并且当没有位被设置时（与第一位被设置时区分），返回-1。
int find_bit(unsigned long long x){ int ret=0, cmp = (x>(1LL<<31))<<5; //32 if true else 0 ret += cmp; x >>= cmp; cmp = (x>(1<<15))<<4; //16 if true else 0 ret += cmp; x >>= cmp; cmp = (x>(1<<7))<<3; //8 ret += cmp; x >>= cmp; cmp = (x>(1<<3))<<2; //4 ret += cmp; x >>= cmp; cmp = (x>(1<<1))<<1; //2 ret += cmp; x >>= cmp; cmp = (x>1); ret += cmp; x >>= cmp; ret += x; return ret-1; }
从技术上讲，这只是返回最重要的设置位的位置。 根据所使用的浮点types，这可以通过使用快速反平方或其他位旋转黑客的较less操作完成
顺便说一句，如果不介意使用编译器builtins，你可以做：
__builtin_popcountll(n-1)或__builtin_ctzll(n)或__builtin_ffsll(n)-1
