如何有效地计算位集中某个位置或更低位置的设置位？

高效计算某个位置或更低位置处的设置位

问题陈述：

给定std::bitset<64>使用任意位值和位位置 X (0-63)，确定对位置 X 或更低的位进行计数的最有效方法，或者如果未设置 X 处的位，则返回 0。

优化解决方案：

以下 C 代码生成高度优化的 x86 ASM，可有效计算指定范围内的设置位范围：

#include <bitset>

int popcount_subset(std::bitset<64> bits, int pos) {
    int high_bits_to_eliminate = 63 - pos;
    bits <<= high_bits_to_eliminate & 63; // Shift to place desired bits at the top
    return (bits[63] ? ~0ULL : 0) & bits.count(); // Broadcast high bit or return 0, then popcount
}

实现细节：

1. 移位操作： 位集左移 63 - pos 以对齐64 位寄存器顶部的所需位。这可以从计数中消除不需要的位。
2. 位广播：使用算术右移将移位后的位集的高位广播到所有位位置。这将创建一个掩码，其中如果设置了高位（即设置了 pos 处的位），则所有位都被设置，否则所有位都被清除。
3. 条件 Popcount： AND 运算将位集与掩码结合起来。如果 pos 处的位被设置，则掩码将为 ~0ULL，从而产生原始的 popcount。否则，掩码将为 0，导致 popcount 为 0。
4. 最佳 ASM： 此代码利用硬件 popcount 指令和位广播，在 64 位架构上生成高效的 x86 ASM

优点：

• 可有效计算指定范围内的设置位。
• 适用于任意位集大小相应地调整常量。
• 在许多架构上生成高度优化的 ASM，包括x86-64 和 ARM64。
• 处理 pos 超出位集大小的情况，而不会出现未定义的行为。

以上是如何有效地计算位集中某个位置或更低位置的设置位？的详细内容。更多信息请关注PHP中文网其他相关文章！