在 int 中查找第 n 个 SET 位

本文介绍了在 int 中查找第 n 个 SET 位的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我想找到第 nth 个最低设置位的位置，而不仅仅是最低设置位.(我不是谈论第 n 位位置的值)

Instead of just the lowest set bit, I want to find the position of the nth lowest set bit. (I'm NOT talking about value on the nth bit position)

例如，假设我有:0000 1101 1000 0100 1100 1000 1010 0000

我想找到设置的第 4 位.然后我希望它返回:0000 0000 0000 0000 0100 0000 0000 0000

And I want to find the 4th bit that is set. Then I want it to return: 0000 0000 0000 0000 0100 0000 0000 0000

如果 popcnt(v) <n，如果这个函数返回 0 是有意义的，但是这种情况下的任何行为对我来说都是可以接受的.

If popcnt(v) < n, it would make sense if this function returned 0, but any behavior for this case is acceptable for me.

如果可能的话，我正在寻找比循环更快的东西.

I'm looking for something faster than a loop if possible.

推荐答案

事实证明，确实可以做到不循环.预先计算这个问题的(至少)8 位版本是最快的.当然，这些表会占用缓存空间，但在几乎所有现代 pc 场景中仍然应该有净加速.在此代码中，n=0 返回最少设置位，n=1 是倒数第二个，等等.

It turns out that it is indeed possible to do this with no loops. It is fastest to precompute the (at least) 8 bit version of this problem. Of course, these tables use up cache space, but there should still be a net speedup in virtually all modern pc scenarios. In this code, n=0 returns the least set bit, n=1 is second-to-least, etc.

使用 __popcnt 的解决方案

有一个使用 __popcnt 内在函数的解决方案(您需要 __popcnt 非常快，否则任何简单循环解决方案的性能增益都将没有实际意义.幸运的是，大多数 SSE4+ 时代的处理器都支持它).

There is a solution using the __popcnt intrinsic (you need __popcnt to be extremely fast or any perf gains over a simple loop solution will be moot. Fortunately most SSE4+ era processors support it).

// 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; }

这说明了分而治之方法的工作原理.

This illustrates how the divide and conquer approach works.

一般解决方案

还有一个通用"架构的解决方案——没有 __popcnt.它可以通过处理 8 位块来完成.您还需要一个查找表来告诉您一个字节的 popcnt:

There is also a solution for "general" architectures- without __popcnt. It can be done by processing in 8-bit chunks. You need one more lookup table that tells you the popcnt of a byte:

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; }

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

This could, of course, be done with a loop, but the unrolled form is faster and the unusual form of the loop would make it unlikely that the compiler could automatically unroll it for you.