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

Question

有一个相对著名的技巧来取消设置单个最右边的位：

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

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

假设相对较大的n（n必须为

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

我已经用大拇指敲了几次我的TAOCP Vol4，但找不到任何灵感。

也许有一些硬件支持？

Answer 1

对于具有 BMI2 的英特尔 x86 CPU，pext 和 pdep 速度很快。Zen3之前的AMD具有非常慢的微编码PEXT/PDEP（https://uops.info/），所以要小心;其他选项在AMD上可能更快，甚至可能是循环中的blsi，或者在popcount上更好地进行二进制搜索（见下文）。
只有英特尔有专用的硬件执行单元，用于 pext/pdep 执行的掩码控制打包/解包，使其时间恒定：1 uop，3 周期延迟，只能在端口 1 上运行。

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

pdep基础知识：pdep（-1ULL， a）==a。从第一个操作数中获取低popcnt（a）位，并将它们存放在a设置位的位置，将再次返回a。

但是，如果您的位源不是全1，而是清除了低N位，则a中的前N个设置位将获取0而不是1。这正是您想要的。

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

<代码>-1ULL

在 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 是单 uop，1 个周期延迟，与更新 FLAG 的传统变量计数移位不同......除非 CL=0）

所以这有3个周期延迟从a-

前端只有3个uop。

一个半相关的BMI2技巧：

pext（a， a）将打包底部的位，如（1ULL

用AND掩码清除其中的低N位，并用pdep展开即可。但这是一种过于复杂且昂贵的方法来创建一个比特源，其中有N个零以上的比特，这对pdep来说才是真正重要的。感谢@harold在这个答案的第一个版本中发现了这一点。

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

当＜code＞popcount（x

完成搜索后，x

高性能popcount在现代CPU上相对广泛可用。（虽然不是x86-64的基线；您仍然需要使用-mpopcnt或-march=native进行编译）。

调整这一点可能需要选择一个可能的起点，并可能使用最大初始步长，而不是纯二进制搜索。从尝试一些初始猜测中获得一些指令级并行性可能有助于缩短延迟瓶颈。