两个整数的位移与异或(XOR)运算的更高效实现方案咨询

实现方案 #

你描述的运算本质是二元有限域GF(2)下的乘法运算，无需额外开辟数组存储位移结果，可以直接在遍历b的二进制位的同时累计异或结果，空间复杂度从O(m)（m为b中1的个数）降到O(1)，同时省去了第二轮数组异或的开销，时间复杂度保持为O(k)（k为b的二进制总位数）。

基础简洁实现 #

思路是逐位扫描b的二进制位，遇到置位的1就将当前位移后的a异或到结果中：

def binary_special_calc(a, b):
    res = 0
    while b > 0:
        # 最低位为1时累加当前a到结果
        if b & 1:
            res ^= a
        # 左移a对应下一位的位移要求，右移b扫描下一位
        a <<= 1
        b >>= 1
    return res

如果你的开发语言是C/C++，写法逻辑完全一致：

unsigned int binary_special_calc(unsigned int a, unsigned int b) {
    unsigned int res = 0;
    while (b) {
        if (b & 1) res ^= a;
        a <<= 1;
        b >>= 1;
    }
    return res;
}

稀疏b场景的优化实现 #

如果b中1的个数远小于总位数，可以用Brian Kernighan算法跳过所有0位，只遍历置位的1，时间复杂度降到O(m)（m为b中1的个数）：

def binary_special_calc_optimized(a, b):
    res = 0
    while b > 0:
        # 提取b最低位的1
        lowest_set_bit = b & -b
        # 计算该1对应的位移位数
        shift = lowest_set_bit.bit_length() - 1
        res ^= a << shift
        # 清除已经处理过的最低位1
        b ^= lowest_set_bit
    return res

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