x = 2 ^ k时最多1位？
可能重复：
有效的按位操作用于计数位或找到最右边的位
我写了一个搜索算法。 为了优化它，我想使用一个32bit int来标记是否可以使用数字32bit int 。 也就是说，如果我有一个州的State ，我可以通过使用以下方式轻松获取所有可能的号码：
x = State & -State
State -= x
但实际上，我需要知道x的1是什么（注意x的二进制形式只有1）？ 例如，如果x = 0000 0100 ，我想知道这是第三个。
我知道我可以通过使用for循环来做到这一点，但似乎它会花费很多时间。
我想知道如果有一种使用按位运算的方法？ static_cast<int>(log2(x))花费很多时间吗？
谢谢你的帮助。
许多CPU都有一个本地硬件指令，像CTZ （“count trailing zeros”）。 GCC通过内置函数__builtin_ctz公开了这一点; 其他编译器应该有类似的设施。
似乎没有人提到这个明显的解决方案 - 使用一个巨大的开关来处理所有可能的两个幂。
下面的代码实现了这一点，加上二进制搜索和除以二。
注意 ：这些函数期望输入将是2的幂; 如果不是，他们可能会回报废话。
#include <inttypes.h>
#include <stdio.h>
int get_exp_switch (uint64_t x)
{
switch (x) {
case (uint64_t)1 << 0: return 0;
case (uint64_t)1 << 1: return 1;
case (uint64_t)1 << 2: return 2;
case (uint64_t)1 << 3: return 3;
case (uint64_t)1 << 4: return 4;
case (uint64_t)1 << 5: return 5;
case (uint64_t)1 << 6: return 6;
case (uint64_t)1 << 7: return 7;
case (uint64_t)1 << 8: return 8;
case (uint64_t)1 << 9: return 9;
case (uint64_t)1 << 10: return 10;
case (uint64_t)1 << 11: return 11;
case (uint64_t)1 << 12: return 12;
case (uint64_t)1 << 13: return 13;
case (uint64_t)1 << 14: return 14;
case (uint64_t)1 << 15: return 15;
case (uint64_t)1 << 16: return 16;
case (uint64_t)1 << 17: return 17;
case (uint64_t)1 << 18: return 18;
case (uint64_t)1 << 19: return 19;
case (uint64_t)1 << 20: return 20;
case (uint64_t)1 << 21: return 21;
case (uint64_t)1 << 22: return 22;
case (uint64_t)1 << 23: return 23;
case (uint64_t)1 << 24: return 24;
case (uint64_t)1 << 25: return 25;
case (uint64_t)1 << 26: return 26;
case (uint64_t)1 << 27: return 27;
case (uint64_t)1 << 28: return 28;
case (uint64_t)1 << 29: return 29;
case (uint64_t)1 << 30: return 30;
case (uint64_t)1 << 31: return 31;
case (uint64_t)1 << 32: return 32;
case (uint64_t)1 << 33: return 33;
case (uint64_t)1 << 34: return 34;
case (uint64_t)1 << 35: return 35;
case (uint64_t)1 << 36: return 36;
case (uint64_t)1 << 37: return 37;
case (uint64_t)1 << 38: return 38;
case (uint64_t)1 << 39: return 39;
case (uint64_t)1 << 40: return 40;
case (uint64_t)1 << 41: return 41;
case (uint64_t)1 << 42: return 42;
case (uint64_t)1 << 43: return 43;
case (uint64_t)1 << 44: return 44;
case (uint64_t)1 << 45: return 45;
case (uint64_t)1 << 46: return 46;
case (uint64_t)1 << 47: return 47;
case (uint64_t)1 << 48: return 48;
case (uint64_t)1 << 49: return 49;
case (uint64_t)1 << 50: return 50;
case (uint64_t)1 << 51: return 51;
case (uint64_t)1 << 52: return 52;
case (uint64_t)1 << 53: return 53;
case (uint64_t)1 << 54: return 54;
case (uint64_t)1 << 55: return 55;
case (uint64_t)1 << 56: return 56;
case (uint64_t)1 << 57: return 57;
case (uint64_t)1 << 58: return 58;
case (uint64_t)1 << 59: return 59;
case (uint64_t)1 << 60: return 60;
case (uint64_t)1 << 61: return 61;
case (uint64_t)1 << 62: return 62;
case (uint64_t)1 << 63: return 63;
default: return 0; // not allowed
}
}
int get_exp_simple (uint64_t x)
{
int i = -1;
do {
i++;
x /= 2;
} while (x > 0);
return i;
}
int get_exp_binsearch (uint64_t x)
{
int left = 63;
int right = 0;
while (left > right) {
int middle = (left + right) / 2;
uint64_t middle_value = (uint64_t)1 << middle;
if (x < middle_value) {
left = middle - 1;
}
else if (x > middle_value) {
right = middle + 1;
}
else {
return middle;
}
}
return left;
}
int main ()
{
uint64_t sum = 0;
for (int j = 0; j < 100000; j++) {
for (int i = 0; i < 64; i++) {
uint64_t x = (uint64_t)1 << i;
int l = get_exp_switch(x);
//int l = get_exp_simple(x);
//int l = get_exp_binsearch(x);
sum += l;
//printf("%" PRIu64 ": %dn", x, l);
}
}
printf("%" PRIu64 "n", sum);
return 0;
}
在我的（64位）系统上使用clang -O2基准测试结果：
get_exp_switch: 0m0.103s
get_exp_simple: 0m0.196s
get_exp_binsearch: 0m0.158s
但是，请注意，当您使用较大的整数（bignum）时，二进制搜索方法将快速开始优于简单方法，并且开关方法的代码大小可能会大得无法接受。
如果您必须使用按位运算符，那么您可以使用位扫描技巧，但大多数编译器对于找到第一个/最后一个位（又名BitScanForward和BitScanReverse）具有内在性，这些功能在现代处理器上非常快，应该使用从技术上讲，这些都是按位操作，即它们在位上操作，它们只是没有操作符形式）。
链接地址: http://www.djcxy.com/p/89581.html下一篇: Moving a bit within a byte using bitfield or bitwise operators