3

我正在尝试找到一个最佳代码来定位长整数（64 位）中的单个位索引。长整数只有一个设置位。（使用C语言）

目前，我只是将整个事情移动一位，然后检查为零。我已阅读有关查找表的信息，但它不适用于整个 64 位。我考虑过检查每个 8 位是否为零，如果不使用查找，但我仍然必须一次移动 8 位。（移位 8 比移位 8 次更好？）

（注意：我正在为移动设备开发，它们 [不足为奇] 很慢）。

4

3 回答 3

5

每当我需要某种方式来操作比特时，我总是在寻找Bit Twiddling Hacks。对于您的问题，它也很少有解决方案。

这个解决方案似乎是快速和最先进的：

并行计算右侧的连续零位（尾随）

unsigned int v;      // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;

对于 N 位字，操作数大致为 3 * lg(N) + 4。

于 2013-02-21T08:57:16.707 回答
5

您可以对设置的位进行二进制搜索：

int bitn(unsigned long long x)
{
    int n = 0;

    if (x >> 32) {
        n += 32;
        x >>= 32;
    }
    if (x >> 16) {
        n += 16;
        x >>= 16;
    }
    if (x >> 8) {
        n += 8;
        x >>= 8;
    }
    if (x >> 4) {
        n += 4;
        x >>= 4;
    }
    if (x >> 2) {
        n += 2;
        x >>= 2;
    }
    if (x >> 1) {
        n += 1;
    }

    return n;
}

GCC 提供了一个内置的__builtin_ctzll(), 来执行此功能（它将利用硬件可能必须快速执行此操作的任何特殊功能）。

于 2013-02-21T09:01:26.037 回答
4

你应该对照你当前的代码检查这个建议（以及这里给出的任何其他建议）——你可能会发现位移是最有效的方法，或者差异很小，在这种情况下你应该优化可读性。

无论如何，请考虑尝试和基准测试，而不是保证更快的东西。

由于只有 64 个可能的值，因此您可以使用以下内容：

int getSetBit (unsigned long x) {
    if (x == 0x8000000000000000UL) return 63;
    if (x == 0x4000000000000000UL) return 62;
    if (x == 0x2000000000000000UL) return 61;
    if (x == 0x1000000000000000UL) return 60;
    if (x == 0x0800000000000000UL) return 59;
    if (x == 0x0400000000000000UL) return 58;
    :
    if (x == 0x0000000000000002UL) return  1;
                                   return  0;
}

您可能会发现这更快，但解决方案通常会受到标准范围之外的很多事情的影响（优化策略、数据缓存、流水线等）。

如果您愿意放弃标准 C，许多环境将优化您可以使用的东西，例如gcc：

int __builtin_ffs (unsigned int x)
// Returns one plus the index of the least significant
//   1-bit of x, or if x is zero, returns zero.

当然，对于那个，您可能必须将其long分成两种int类型并单独检查每种类型，例如（未经测试，但您应该了解总体思路）：

if (x < 0x80000000UL) return __builtin_ffs((unsigned int)x) - 1;
return __builtin_ffs((unsigned int)(x>>32)) -1 + 32;

或者，__builtin_clzl()可以操纵来自的输出来为您提供位位置（它为您提供前导零计数）并且它unsigned long已经可以使用。您可以在此处gcc查看内置插件。

于 2013-02-21T08:54:50.493 回答