我需要从右往左在一个二进制数中找到第一个被设置的位; 我想出了这个解决方案:
int cnt=0;
while (number& 1 ==0)
{
cnt++;
number>>=1;
}
有没有更好的方法?一些巧妙的位操作技巧吗?
我需要从右往左在一个二进制数中找到第一个被设置的位; 我想出了这个解决方案:
int cnt=0;
while (number& 1 ==0)
{
cnt++;
number>>=1;
}
有没有更好的方法?一些巧妙的位操作技巧吗?
处理器可能直接有指令来找到它:
Windows/MSVC:
GCC:
这些通常直接映射到本机硬件指令。因此,它们比其他方法更快。
但是由于没有C/C++的功能,它们只能通过编译器内置函数访问。
您可以手动执行以下方式:
n & (n - 1)
是一种去除最右侧设置位的技巧。
因此,n - (n & n - 1)
将返回一个只有最右侧设置位的数字。
然后对结果进行 'log2' 运算即可得到解决方案:此链接可能会有所帮助
或者您可以使用所有 1 << k
的 switch case 语句来获得解决方案。
switch (n - (n & n - 1)) {
case 0: ...
case 1 << 0: return 0;
case 1 << 1: return 1;
...
}
Bit Twiddling Hacks提供了一系列出色的位操作技巧,并附有性能/优化讨论。对于您的问题(来自该网站),您可以使用乘法和查找策略:
unsigned int c = number; // your input number
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)((c & -c) * 0x077CB531U)) >> 27];
number
的第一个设置位将是 t
的唯一设置位,因此您只需要在 switch 中使用 32 或 64 个情况。 - neverhoodboybsf
,bsr
)就是目标。 - neverhoodboynumber & -number
,对吧?或者是有一些晦涩的基于标准的反对意见吗? - harold你的代码
int cnt=0;
while (number& 1 ==0)
{
cnt++;
number>>=1;
}
有一个错误。例如,如果数字等于0,则循环将无限执行。
我会按照以下方式重写它
int cnt = 0;
if ( number ) while ( !( number & ( 1 << cnt++ ) ) );
我不确定被接受的答案是否正确。我刚刚测试了朴素循环和(num & -num)解决方案。它们的速度都是一样的。朴素循环代码更少。我使用以下方式构建:
来自MinGW的gcc 4.7.2,在Win 7上 gcc test.c -o test.exe -std=c99 -Wall -O2
这是我的代码(它可能有一些边角情况的错误,但我认为时间大致上是有效的)。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NUM_NUMS 65536
int find_first_bits(unsigned nums[NUM_NUMS])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < 10000; j++) {
for (int i = 0; i < NUM_NUMS; i++) {
switch (nums[i] & -nums[i]) {
case (1<<0): total += 1; break;
case (1<<1): total += 2; break;
case (1<<2): total += 3; break;
case (1<<3): total += 4; break;
case (1<<4): total += 5; break;
case (1<<5): total += 6; break;
case (1<<6): total += 7; break;
case (1<<7): total += 8; break;
case (1<<8): total += 9; break;
case (1<<9): total += 10; break;
case (1<<10): total += 11; break;
case (1<<11): total += 12; break;
case (1<<12): total += 13; break;
case (1<<13): total += 14; break;
case (1<<14): total += 15; break;
case (1<<15): total += 16; break;
case (1<<16): total += 17; break;
case (1<<17): total += 18; break;
case (1<<18): total += 19; break;
case (1<<19): total += 20; break;
case (1<<20): total += 21; break;
case (1<<21): total += 22; break;
case (1<<22): total += 23; break;
case (1<<23): total += 24; break;
case (1<<24): total += 25; break;
case (1<<25): total += 26; break;
case (1<<26): total += 27; break;
case (1<<27): total += 28; break;
case (1<<28): total += 29; break;
case (1<<29): total += 30; break;
case (1<<30): total += 31; break;
case (1<<31): total += 32; break;
}
}
}
return total;
}
int find_first_bits2(unsigned nums[NUM_NUMS])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < 10000; j++) {
for (int i = 0; i < NUM_NUMS; i++) {
unsigned mask = 1;
for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) {
if (nums[i] & mask) {
total += cnt;
break;
}
}
}
}
return total;
}
int main() {
// Create some random data to test
unsigned nums[NUM_NUMS];
for (int i = 0; i < NUM_NUMS; i++) {
nums[i] = rand() + (rand() << 15);
}
clock_t start_time, end_time;
int result;
start_time = clock();
result = find_first_bits(nums);
end_time = clock();
printf("Time = %.5f, result = %d\n", (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits2(nums);
end_time = clock();
printf("Time = %.5f, result = %d\n", (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
}