位操作--为第一个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

最近的一些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 2

猜测位，并使用内置的波普计数来测试猜测。如果我们认为内置的波普计数为O(1)，那么复杂度将是O(log )(带有二进制搜索)。

Answer 3

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