位操作——为前 N 个设置位生成掩码

Question

我想知道是否有针对以下问题的有效算法实现：

给定一个无符号整数 U，制作一个掩码，选择 U 的前 N 位已设置。（从右到左，从低位到高位）

例如：

f(U=1111, N=2) -> 0011
f(U=1010, N=2) -> 1010
f(U=1110, N=2) -> 0110
f(U=0111, N=2) -> 0011
f(U=0011, N=2) -> 0011

大多数处理器都有“查找第一个设置位”或类似的指令，所以我认为在最坏的情况下我可以调用 N 次，但是否可以做得更好？

Answer 1

int getmask(unsigned int U, int n) {
      unsigned int m = U;
      do {
        m &= m - 1;
      } while(m && --n);
      return U & ~m; 
}

Answer 2

最近的一些 CPU 有 pdep 指令，使用它很容易：

m = bitmask of n ones
return pdep(m, x)

否则，@olegarch 的解决方案中的逐步方法可能是不可避免的。稍微少一点的指令如下：

unsigned getmask(unsigned x, int n) {
    unsigned x1 = -x;
    for (int i = 0; i < n - 1; ++i)
        x1 = x1 - (x ^ x1);
    return x & x1;
}

Answer 3

猜位并使用内置的 popcount 来测试猜测。如果我们将内置的 popcount 视为 O(1)，那么复杂度将是 O(log N)（使用二分查找）。

Bit manipulation -- generate mask for first N set bits