如何有效地使用位操作找到 64 位值中唯一设置位的位置？
How to find the position of the only-set-bit in a 64-bit value using bit manipulation efficiently?
就说我有一个 uint64_t 类型的值，被视为八位字节序列（1 个八位字节 = 8 位）。已知 uint64_t 值仅在 MSB 位置包含一个 set 位 。因此，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
我需要一个 returns 设置位 位置的快速函数，但是 returns 0 如果没有设置位。
如果可能的话，我希望它既没有循环也没有分支。
如果可以使用 POSIX，请使用 strings.h 中的 ffs() 函数（而不是 string.h！）。它 returns 最低有效位集（一个索引）的位置，如果参数为零，则为零。在大多数实现中，对 ffs() 的调用被内联并编译成相应的机器指令，如 x86 上的 bsf。 glibc 也有 ffsll() 用于 long long 参数，如果可用的话应该更适合你的问题。
如果你想要一个算法而不是一个内置的算法，这个就可以了。它产生最高有效 1 位的位数，即使设置了不止一位。它通过迭代将所考虑的位范围分成两半来缩小位置，测试上半部分是否设置了任何位，如果有则将那一半作为新的位范围，否则将下半部分作为新的位范围.
#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;
}
值 mod 0x8C 为每个案例生成一个唯一值。
这个值mod 0x11 仍然是唯一的。
table 中的第二个值是结果 mod 0x11。
128 9
32768 5
8388608 10
2147483648 0
549755813888 14
140737488355328 2
36028797018963968 4
9223372036854775808 15
所以一个简单的查找 table 就足够了。
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}
这是一个可移植的解决方案，但是，它比利用 clz（计算前导零）等专用指令的解决方案要慢。我在算法的每一步都添加了注释来解释它是如何工作的。
#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 的方法，所需的功能可以更简洁地表达如下：
/* 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
将该值乘以精心设计的 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
clang 在三个 x86_64 指令中实现了这一点，不包括帧设置和清理：
_field_set:
push %rbp
mov %rsp,%rbp
movabs [=11=]x20406080a0c0e1,%rax
imul %rdi,%rax
shr [=11=]x3c,%rax
pop %rbp
retq
请注意，任何其他输入的结果几乎都是随机的。 （所以不要那样做。）
我认为没有任何可行的方法可以将此方法直接扩展到 7..63 范围内的 return 值（常量的结构不允许这样做），但您可以转换通过将结果乘以 7，将结果调整到该范围。
关于这个常量是如何设计的：我从以下观察开始：
- 无符号乘法对大多数 CPUs 来说是一个快速的运算，并且可以产生有用的效果。我们应该使用它。 :)
- 任何东西乘以零都会得到零。由于这与无位设置输入的预期结果相匹配，因此我们目前表现良好。
- 将任何值乘以
1ULL<<63（即您的 "pos=63" 值）只能得到相同的值或零。 （它不可能有任何低位设置，也没有高位可以更改。）因此，我们必须找到一些方法将这个值视为正确的结果。
- 使该值成为其自身正确结果的一种简便方法是将其右移 60 位。这将它向下移动到“8”，这是一个足够方便的表示。我们可以继续将其他输出编码为 1 到 7。
将我们的常量乘以每个其他位字段相当于将其左移等于其 "position" 的位数。右移 60 位导致仅给定位置左侧的 4 位出现在结果中。因此，我们可以创建除一个 之外的所有案例 ，如下所示：
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 的正确结果；这个常数是偶数，所以用它乘以那个输入得到零。我们必须设置最低位（即 constant |= 1ULL）才能使这种情况起作用，从而为我们提供 0x20406080a0c0e1ULL.
的最终值
请注意，可以修改上面的构造以对结果进行不同的编码。但是，8 的输出如上所述是固定的，所有其他输出必须适合 4 位（即 0 到 15）。
C++ 标签已删除，但这里仍然是一个可移植的 C++ 答案，因为您可以使用 C++ 编译它并使用 extern C 接口：
如果你有 2 的幂并且你减去一个你最终得到一个二进制数，其设置位数等于位置
在std::bitset成员函数count[中，包装了一种计算设置位数（二进制1s）的方法，大概是stl的每个实现最有效的方法=22=]
请注意，您的规范已针对 0 或 1 进行了 0 return 编辑，因此我添加了 as_specified_pos 以满足此要求。就我个人而言，我会在传递 0 时将其 return 保留为 64 的自然值，以便能够区分，并提高速度。
以下代码应该是非常可移植的，并且很可能由编译器供应商针对每个平台进行了优化：
#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;
}
在 Linux 上使用 g++ 我得到以下反汇编代码：
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）。
大多数编译器都有内部函数来轻松生成它们。见下文wikipedia page.
00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 pos = 7
..., but returns 0 if there is no bit that is set.
这将 return 如果设置了第一位或未设置位，则相同；然而，在 x86_64 上，这正是 bsrq 所做的：
int bsrq_x86_64(uint64_t x){
int ret;
asm("bsrq %0, %1":"=r"(ret):"r"(x));
return ret;
}
但是；如果设置了第一位，它也将 return 0；这是一种方法，它将 运行 在恒定时间内（无循环或分支）和 returns -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;
}
从技术上讲，这只是 return 最重要设置位的位置。根据使用的浮点类型，使用快速平方反比或其他 bit twiddling hacks
可以在更少的操作中完成
顺便说一句，如果不介意使用内置编译器，你可以这样做：
__builtin_popcountll(n-1) 或 __builtin_ctzll(n) 或 __builtin_ffsll(n)-1
一个简单的查找解决方案。 m=67 是值 (1<<k)%m 都不同的最小整数，for k<m。带有（python转座码）：
lut = [-1]*67
for i in range(0,64) : lut[(1<<i)%67] = i
然后 lut[a%67] 如果 a = 1<<k 给出 k。 -1 值未使用。
就说我有一个 uint64_t 类型的值，被视为八位字节序列（1 个八位字节 = 8 位）。已知 uint64_t 值仅在 MSB 位置包含一个 set 位 。因此，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
我需要一个 returns 设置位 位置的快速函数，但是 returns 0 如果没有设置位。
如果可能的话，我希望它既没有循环也没有分支。
如果可以使用 POSIX，请使用 strings.h 中的 ffs() 函数（而不是 string.h！）。它 returns 最低有效位集（一个索引）的位置，如果参数为零，则为零。在大多数实现中，对 ffs() 的调用被内联并编译成相应的机器指令，如 x86 上的 bsf。 glibc 也有 ffsll() 用于 long long 参数，如果可用的话应该更适合你的问题。
如果你想要一个算法而不是一个内置的算法，这个就可以了。它产生最高有效 1 位的位数，即使设置了不止一位。它通过迭代将所考虑的位范围分成两半来缩小位置，测试上半部分是否设置了任何位，如果有则将那一半作为新的位范围，否则将下半部分作为新的位范围.
#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;
}
值 mod 0x8C 为每个案例生成一个唯一值。
这个值mod 0x11 仍然是唯一的。
table 中的第二个值是结果 mod 0x11。
128 9
32768 5
8388608 10
2147483648 0
549755813888 14
140737488355328 2
36028797018963968 4
9223372036854775808 15
所以一个简单的查找 table 就足够了。
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}
这是一个可移植的解决方案，但是，它比利用 clz（计算前导零）等专用指令的解决方案要慢。我在算法的每一步都添加了注释来解释它是如何工作的。
#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
[稍后更新]
/* 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
将该值乘以精心设计的 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
clang 在三个 x86_64 指令中实现了这一点，不包括帧设置和清理：
_field_set:
push %rbp
mov %rsp,%rbp
movabs [=11=]x20406080a0c0e1,%rax
imul %rdi,%rax
shr [=11=]x3c,%rax
pop %rbp
retq
请注意，任何其他输入的结果几乎都是随机的。 （所以不要那样做。）
我认为没有任何可行的方法可以将此方法直接扩展到 7..63 范围内的 return 值（常量的结构不允许这样做），但您可以转换通过将结果乘以 7，将结果调整到该范围。
关于这个常量是如何设计的：我从以下观察开始：
- 无符号乘法对大多数 CPUs 来说是一个快速的运算，并且可以产生有用的效果。我们应该使用它。 :)
- 任何东西乘以零都会得到零。由于这与无位设置输入的预期结果相匹配，因此我们目前表现良好。
- 将任何值乘以
1ULL<<63（即您的 "pos=63" 值）只能得到相同的值或零。 （它不可能有任何低位设置，也没有高位可以更改。）因此，我们必须找到一些方法将这个值视为正确的结果。 - 使该值成为其自身正确结果的一种简便方法是将其右移 60 位。这将它向下移动到“8”，这是一个足够方便的表示。我们可以继续将其他输出编码为 1 到 7。
将我们的常量乘以每个其他位字段相当于将其左移等于其 "position" 的位数。右移 60 位导致仅给定位置左侧的 4 位出现在结果中。因此，我们可以创建除一个 之外的所有案例 ，如下所示：
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 的正确结果；这个常数是偶数，所以用它乘以那个输入得到零。我们必须设置最低位（即 constant |= 1ULL）才能使这种情况起作用，从而为我们提供 0x20406080a0c0e1ULL.
请注意，可以修改上面的构造以对结果进行不同的编码。但是，8 的输出如上所述是固定的，所有其他输出必须适合 4 位（即 0 到 15）。
C++ 标签已删除，但这里仍然是一个可移植的 C++ 答案，因为您可以使用 C++ 编译它并使用 extern C 接口：
如果你有 2 的幂并且你减去一个你最终得到一个二进制数，其设置位数等于位置
在std::bitset成员函数count[中，包装了一种计算设置位数（二进制1s）的方法，大概是stl的每个实现最有效的方法=22=]
请注意，您的规范已针对 0 或 1 进行了 0 return 编辑，因此我添加了 as_specified_pos 以满足此要求。就我个人而言，我会在传递 0 时将其 return 保留为 64 的自然值，以便能够区分，并提高速度。
以下代码应该是非常可移植的，并且很可能由编译器供应商针对每个平台进行了优化：
#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;
}
在 Linux 上使用 g++ 我得到以下反汇编代码：
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）。
大多数编译器都有内部函数来轻松生成它们。见下文wikipedia page.
00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 pos = 7..., but returns 0 if there is no bit that is set.
这将 return 如果设置了第一位或未设置位，则相同；然而，在 x86_64 上，这正是 bsrq 所做的：
int bsrq_x86_64(uint64_t x){
int ret;
asm("bsrq %0, %1":"=r"(ret):"r"(x));
return ret;
}
但是；如果设置了第一位，它也将 return 0；这是一种方法，它将 运行 在恒定时间内（无循环或分支）和 returns -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;
}
从技术上讲，这只是 return 最重要设置位的位置。根据使用的浮点类型，使用快速平方反比或其他 bit twiddling hacks
可以在更少的操作中完成顺便说一句，如果不介意使用内置编译器，你可以这样做：
__builtin_popcountll(n-1) 或 __builtin_ctzll(n) 或 __builtin_ffsll(n)-1
一个简单的查找解决方案。 m=67 是值 (1<<k)%m 都不同的最小整数，for k<m。带有（python转座码）：
lut = [-1]*67
for i in range(0,64) : lut[(1<<i)%67] = i
然后 lut[a%67] 如果 a = 1<<k 给出 k。 -1 值未使用。