c - 位操作——为前 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;
}