如何重置位掩码中的第N个已置位比特位？

给定一个位掩码（其中已置位M个比特，即popcount(bit_mask) == M），需要生成M个不同的位掩码，每个掩码会将原掩码中的一个已置位比特翻转——这个需求可以简化为重置位掩码中的第N个已置位比特位。

示例 #

以位掩码0xE7（二进制0b11100111，popcount(0xE7) == 6）为例，生成的6个目标掩码如下：

0xE6（第1个已置位比特被翻转）
0xE5（第2个已置位比特被翻转）
0xE3（第3个已置位比特被翻转）
0xC7（第4个已置位比特被翻转）
0xA7（第5个已置位比特被翻转）
0x67（第6个已置位比特被翻转）

原方案的局限性 #

当前使用Intel处理器的并行位存入指令（_pdep_u32）实现，虽然简洁但不具备可移植性：

_pdep_u32(~0x1U, 0xE7U) == 0xE6U
_pdep_u32(~0x2U, 0xE7U) == 0xE5U
_pdep_u32(~0x4U, 0xE7U) == 0xE3U
_pdep_u32(~0x8U, 0xE7U) == 0xC7U
_pdep_u32(~0x10U, 0xE7U) == 0xA7U
_pdep_u32(~0x20U, 0xE7U) == 0x67U

可移植的实现方案 #

核心思路是：先定位到第N个已置位比特的掩码，再通过位运算将其重置。以下是通用的实现代码：

#include <stdint.h>

// 获取位掩码中第N个已置位比特的单独掩码（N从1开始计数）
uint32_t get_nth_set_bit_mask(uint32_t bit_mask, int n) {
    uint32_t temp = bit_mask;
    // 清除前N-1个已置位比特
    for (int i = 0; i < n - 1; ++i) {
        temp &= temp - 1;
    }
    // 提取剩余的最低置位比特的掩码
    temp &= -temp;
    return temp;
}

// 重置位掩码中的第N个已置位比特
uint32_t reset_nth_set_bit(uint32_t bit_mask, int n) {
    uint32_t nth_bit_mask = get_nth_set_bit_mask(bit_mask, n);
    return bit_mask & ~nth_bit_mask;
}

验证示例

调用上述函数测试0xE7的情况：

reset_nth_set_bit(0xE7, 1); // 返回 0xE6
reset_nth_set_bit(0xE7, 2); // 返回 0xE5
reset_nth_set_bit(0xE7, 3); // 返回 0xE3
reset_nth_set_bit(0xE7, 4); // 返回 0xC7
reset_nth_set_bit(0xE7, 5); // 返回 0xA7
reset_nth_set_bit(0xE7, 6); // 返回 0x67

原理说明 #

1. temp &= temp - 1：每次操作会清除temp中最低的已置位比特，循环N-1次后，temp中仅保留第N个及更高位的已置位比特。
2. temp &= -temp：利用补码特性，提取temp中最低的已置位比特的单独掩码（例如，0xE7经过3次清除后得到0xE0，0xE0 & -0xE0得到0x80，对应第4个已置位比特）。
3. bit_mask & ~nth_bit_mask：将原掩码中第N个已置位比特重置为0，其余比特保持不变。

这个方案不依赖特定CPU的指令集，在绝大多数编译器和平台上都能正常运行。

内容的提问来源于stack exchange，提问作者Jeremy Wong