如何用纯位运算实现Python函数清除二进制中的孤立1？

要解决这个问题，核心是先找出所有孤立的1（即左右相邻位都为0的1），然后将这些位清零即可。完全用位运算实现的话，可以分两步走：

步骤分析 #

1. 生成孤立1的掩码：
   一个位是孤立1的条件是：自身为1，且左边的位（左移一位后的对应位）为0，同时右边的位（右移一位后的对应位）为0。用位运算表达就是：

   isolated = x & ~(x << 1) & ~(x >> 1)
   

   • x << 1：把原数左移一位，相当于检查每个位的左侧是否有1；
   • ~(x << 1)：取反后，得到左侧位为0的所有位置；
   • ~(x >> 1)：同理，取反后得到右侧位为0的所有位置；
   • 三者相与，最终得到的就是所有孤立1的位置（这些位为1，其余为0）。

2. 清除孤立1：
   把原数中孤立1的位置清零，直接用原数和孤立掩码的反值相与即可：

   result = x & ~isolated
   

完整函数实现 #

def remove_isolated_ones(x):
    # 计算孤立1的掩码
    isolated = x & ~(x << 1) & ~(x >> 1)
    # 清除孤立1
    return x & ~isolated

测试示例 #

print(bin(remove_isolated_ones(0b11010)))  # 输出 0b11000
print(bin(remove_isolated_ones(0b10101)))  # 输出 0b0

补充说明 #

• 对于正整数输入，无需考虑符号位影响，Python的整数补码表示不干扰结果；
• 所有操作均为纯位运算，未使用循环、列表或第三方库，完全符合要求。

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