如何取消设置最右边的 N 个设置位

Question

有一个相对知名的技巧可以取消单个最右边的位：

y = x & (x - 1) // 0b001011100 & 0b001011011 = 0b001011000 :)

我发现自己有一个紧密的循环来清除最右边的 n 位，但是有更简单的代数技巧吗？

假设n相对较大（n必须是<64 for 64bit integers, but it's often on the order of 20-30).

// x = 0b001011100 n=2
for (auto i=0; i<n; i++) x &= x - 1;
// x = 0b001010000

我翻阅了 TAOCP Vol4 好几次，但找不到任何灵感。

也许有一些硬件支持？

Answer 1

对于具有 BMI2 的 Intel x86 CPU，

pext

和

pdep

速度很快。 Zen3 之前的 AMD 具有非常慢的微编码 PEXT/PDEP (https://uops.info/)，所以要小心这一点；其他选项在 AMD 上可能会更快，甚至可能在循环中

blsi

，或者更好地在 popcount 上进行二分搜索（见下文）。
只有 Intel 拥有专用硬件执行单元，用于 pext/pdep 执行的掩码控制打包/解包，使其恒定时间：1 uop，3 个周期延迟，只能在端口 1 上运行。

我不知道其他 ISA 具有类似的位打包硬件操作。

---

pdep

基础知识：

pdep(-1ULL, a) == a

。从第一个操作数中取出 popcnt(a) 的低位，并将它们存放在

a

已设置位的位置，将再次返回

a

。

但是，如果您的位源清除了低 N 位，而不是全 1，则

a

中的前 N 个设置位将获取 0 而不是 1。这正是您想要的。

uint64_t unset_first_n_bits_bmi2(uint64_t a, int n){
    return _pdep_u64(-1ULL << n, a);
}

-1ULL << n

适用于 C 中的 n=0..63。x86 asm 标量移位指令掩盖了它们的计数（有效地

&63

），所以这就是 可能 对于更大的

n

的 C 未定义行为会发生什么。如果您关心，请在源代码中使用

n&63

，以便在 C 中明确定义行为，并且它仍然可以编译为直接使用计数的移位指令。

在 Godbolt 上使用简单的循环参考实现，表明它们对于样本输入

a

和

n

产生相同的结果。

GCC 和 clang 都以显而易见的方式编译它，如下所示：

# GCC10.2 -O3 -march=skylake
unset_first_n_bits_bmi2(unsigned long, int):
        mov     rax, -1
        shlx    rax, rax, rsi
        pdep    rax, rax, rdi
        ret

（SHLX 是单微指令，1 个周期延迟，与更新 FLAGS 的传统可变计数移位不同...除非 CL=0。更新：在 uops.info 测量中，Alder Lake P 核心的

shlx

有 3 个周期延迟，并且只有 1c 吞吐量，即使它们对于 2 个端口中的任何一个都是 1 uop。我不知道为什么；

shl reg, cl

的非标志部分仍然是 1c 延迟。）

因此，从

a

-> 输出（仅 pdep）有 3 个周期延迟
以及从

n

-> 输出（shlx、pdep）的 4 个周期延迟。

前端只有 3 uops。

---

半相关的BMI2技巧：

pext(a,a)

将把位打包在底部，类似于

(1ULL<<popcnt(a)) - 1

，但如果设置了所有位，则不会溢出。

使用 AND 掩码清除其中的低 N 位，然后使用

pdep

进行扩展就可以了。但这是一种过于复杂且昂贵的方式来创建具有足够多的高于 N 个零的位源，而这对于 pdep 来说才是真正重要的。感谢@harold 在这个答案的第一个版本中发现了这一点。

---

没有快速 PDEP：也许可以通过二分搜索来找到正确的 popcount

@Nate 建议进行 二进制搜索来清除多少低位 可能是 pdep 的一个很好的替代方案。

当

popcount(x>>c) == popcount(x) - N

时停止，找出要清除的低位数，最好使用

c

的无分支更新。 （例如

c = foo ? a : b

通常编译为 cmov）。

完成搜索后，

x & (-1ULL<<c)

使用该计数，或者只是

tmp << c

移回您已有的

x>>c

结果。直接使用右移比生成新掩码并在每次迭代中使用它更便宜。

高性能 popcount 在现代 CPU 上相对广泛地可用。 （尽管 不是 x86-64 的基线；您仍然需要使用

-mpopcnt

或

-march=native

进行编译）。

调整这一点可能涉及选择一个可能的起点，并且可能使用最大初始步长而不是纯二分搜索。通过尝试一些初步猜测来获得一些指令级并行性可能有助于缩短延迟瓶颈。