时间戳

首页 > 解决方案 > 交换位算法中的位掩码

algorithm - 交换位算法中的位掩码

问题描述

完全理解一个基本算法有点麻烦，它接受一个数字 x 并交换位置 i 和 j 的位。算法是这个众所周知的

def swap_bits(x, i, j):
    if (x >> i) & 1 != (x >> j) & 1:
        bit_mask = (1 << i) | (1 << j)
        x ^= bit_mask
    return x

据我了解，算法的工作原理是

  1. 检查位置 i 和 j 的位是否不同。如果没有，我们就完成了 bc 交换相同的位与什么都不做是一样的
  2. 如果它们不同，那么我们通过翻转位来交换它们。我们可以用 XOR 来做到这一点。

我不完全理解的是位掩码的构造是如何工作的。我知道掩码的目标是识别我们想要切换的位子集，但为什么(1 << i) | (x << j)要这样做呢？我想我看到它一秒钟，然后我失去了它。

编辑：

我想我现在看到了。我们只是创建了两个二进制数，一个在位置上设置了一个位，一个在i位置上设置了一个位j。通过对这些进行或运算，我们得到了一个在i 和 j位置设置位的数字。我们可以将此掩码应用于我们的输入x，因为x ^ 1= 0 时x = 1和 1 时x = 0交换位。

标签： algorithmbinary

解决方案

您最初的直觉认为某些东西看起来很可疑是正确的。有一个错字：

> def swap_bits(x, i, j):
...     if (x >> i) & 1 != (x >> j) & 1:
...         bit_mask = (1 << i) | (x << j)
...         x ^= bit_mask
...     return x
... 
>>> swap_bits(0x55555, 1, 2)
1048579
>>> hex(swap_bits(0x55555, 1, 2))
'0x100003'
>>>

答案应该是 0x55553。一个更正的版本会有

  bit_mask = (1 << i) | (1 << j)

我同意其中一种评论，即这种方法要求实现if-less。在 C 中：

unsigned swap_bits(unsigned val, int i, int j) {
  unsigned b = ((val >> i) ^ (val >> j)) & 1;
  return ((b << i) | (b << j)) ^ val;
}

推荐阅读