事实证明，确实可以无循环执行此操作。预计算此问题的（至少）8位版本最快。当然，这些表会占用高速缓存空间，但是在几乎所有现代PC方案中，仍然应该有净加速。在此代码中，n
= 0返回最低设置位，n = 1倒数第二，以此类推。

__popcnt解决方案

有一个使用__popcnt内在函数的解决方案（您需要__popcnt才能非常快，否则通过简单循环解决方案获得的任何性能提升都是没有意义的。幸运的是，大多数SSE4
+时代的处理器都支持它）。

// lookup table for sub-problem: 8-bit v
byte PRECOMP[256][8] = { .... } // PRECOMP[v][n] for v < 256 and n < 8

ulong nthSetBit(ulong v, ulong n) {
    ulong p = __popcnt(v & 0xFFFF);
    ulong shift = 0;
    if (p <= n) {
        v >>= 16;
        shift += 16;
        n -= p;
    }
    p = __popcnt(v & 0xFF);
    if (p <= n) {
        shift += 8;
        v >>= 8;
        n -= p;
    }

    if (n >= 8) return 0; // optional safety, in case n > # of set bits
    return PRECOMP[v & 0xFF][n] << shift;
}

这说明了分而治之方法是如何工作的。

通用解决方案

还有一种针对“通用”体系结构的解决方案-不使用__popcnt。可以通过处理8位块来完成。您还需要一个查找表来告诉您一个字节的popcnt：

byte PRECOMP[256][8] = { .... } // PRECOMP[v][n] for v<256 and n < 8
byte POPCNT[256] = { ... } // POPCNT[v] is the number of set bits in v. (v < 256)

ulong nthSetBit(ulong v, ulong n) {
    ulong p = POPCNT[v & 0xFF];
    ulong shift = 0;
    if (p <= n) {
        n -= p;
        v >>= 8;
        shift += 8;
        p = POPCNT[v & 0xFF];
        if (p <= n) {
            n -= p;
            shift += 8;
            v >>= 8;
            p = POPCNT[v & 0xFF];
            if (p <= n) {
                n -= p;
                shift += 8;
                v >>= 8;
            }
        }
    }

    if (n >= 8) return 0; // optional safety, in case n > # of set bits
    return PRECOMP[v & 0xFF][n] << shift;
}

当然，这可以通过循环来完成，但是展开形式更快，并且异常形式的循环会使编译器不太可能为您自动展开它。