位操作 -- 生成前N个置位的掩码

Question

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

给定一个无符号整数U，生成一个掩码(mask)，用于选择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次，但是有没有更好的方法呢？

- Joseph Garvin

---

log(N) 可能是可行的。步骤更少，但更好吗？ - chux - Reinstate Monica

显而易见的问题：空间有任何限制吗？ - Ulrich Eckhardt

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

- Falk Hüffner

---

最好描述PDEP指令执行的功能，并引用或链接相关文档。 - Eric Postpischil

PDEP和掩码的结合非常有效。有关PDEP的其他文档，请参考：https://www.felixcloutier.com/x86/pdep - Joseph Garvin

PDEP 的唯一缺点是在 x86 以外的平台上无法移植，并且在 AMD（Zen，Zen2）上性能较差 :( 但我可以接受这一点... - Joseph Garvin

更新：Zen3现在硬件上有PDEP（Zen2是微码），因此速度很快。 - Joseph Garvin

Answer 2

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

- גלעד ברקן

---

你能解释得更详细一些吗？我不明白你的意思。 - Joseph Garvin

@JosephGarvin 我们创建了一个掩码，(1 << i) - 1。这是一系列设置的位，直到但不包括第i位。然后我们将该掩码与U进行AND（&）运算。如果我们得到正确的i，那么我们就有了你要找的答案。猜测是在单调递增的范围内进行的（popcount，在AND操作后剩余的设置位数），随着i的增加而增加，这意味着我们可以使用二分查找在log（N）时间内找到正确的i。 - גלעד ברקן

Answer 3

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

- olegarch

---

根据问题陈述，“U” 应该是无符号的。 - Eric Postpischil

这个问题寻求的是比先找到前N个最低位比特更好的解决方案，但实际上这个解决方案就是这样做的，尽管它使用的是普通的C代码而不是查找第一个比特扩展。因此，这可能不是OP所请求的内容。 - Eric Postpischil

将“int”更改为“unsigned int”。使用哪种int类型并不重要。无论如何，都没有比较“<>”或算术移位。 - olegarch

类型很重要，因为当 m 是 INT_MIN 时，m-1 的行为在 C 标准中没有定义。 - Eric Postpischil