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

Question

有一个相对众所周知的技巧可以取消设置最右侧的单个位:

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

我发现自己有一个紧密的循环来清除最右边的 n 位，但是有没有更简单的代数技巧？
假设 n 相对较大(对于 64 位整数，n 必须<64，但通常在 20-30 的数量级)。

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

我已经翻了几次我的 TAOCP Vol4a，但找不到任何灵感。
也许有一些硬件支持？

Answer 1

对于具有 BMI2 的 Intel x86 CPU， pext 和 pdep 很快。 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再次回来。
但是，如果您的位源不是全 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 << n适用于 C 中的 n=0..63。x86 asm 标量移位指令掩盖了它们的计数(实际上是 &63 )，所以这可能是更大 n 的 C 未定义行为会发生的情况.如果您在意，请使用 n&63在源代码中，因此行为在 C 中定义良好，并且它仍然可以编译为直接使用计数的移位指令。
On 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 周期延迟，与更新 FLAGS 的传统可变计数移位不同......除非 CL=0)
所以这有来自 a 的 3 个周期延迟-> 输出(只是 pdep)
和来自 n 的 4 个周期延迟-> 输出(shlx，pdep)。
并且前端只有 3 uop。

一个半相关的 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 进行编译)。
调整这可能涉及选择一个可能的起点，并且可能使用最大初始步长而不是纯二分搜索。从尝试一些初始猜测中获得一些指令级并行性可能有助于缩短延迟瓶颈。