在int中找到第n个SET位

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

__popcnt解决方案

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

// lookup table for sub-problem: 8-bit vbyte PRECOMP[256][8] = { .... } // PRECOMP[v][n] for v < 256 and n < 8ulong 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 < 8byte 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;}

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