algorithm - 清除最低有效位在这个算法中是如何重复工作的？

Question

以下函数确定将整数 A 转换为整数 B 需要翻转的位数。我已经用不同的方法解决了它，但是当我阅读这个解决方案时，我不明白它。它显然有效，但我的问题是为什么？

def bit_swap_required(a: int, b: int) -> int:
    count, c = 0, a ^ b
    while c:
        count, c = count + 1, c & (c - 1)
    return count

我理解为什么我们要执行 a^b。它在我们需要翻转的每个地方都给了我们一个“1”。但是，重复执行 c & (c-1) 是如何为您提供数字中“1”的确切数量的？

Answer 1

c - 1 取消设置 c 的二进制表示中的最低有效位，并将所有未设置的位设置到该位的右侧。

当您使用 c 二进制和 c - 1 时，您有效地取消设置了最低有效设置位和最低有效设置位右侧的所有位。换句话说，c 中的最低有效设置位及其右侧的所有内容都变为零。

您将其视为一个，这是正确的。因为它只是来自 a ^ b 的一组位。

现在，你继续这个操作，直到c变成零，操作的次数就是c中设置的位数，也就是之间不同的位数>a 和 b。

举例说明 c - 1 对 c 的二进制表示的作用:

c = 6, in binary 110
c-1 = 5, in binary 101
(c-1) & (c) = 110 & 101 = 100
The above is one iteration of the loop

Next iteration
c = 4, in binary 100
c-1 = 3, in binary 011
(c-1) & (c) = 100 & 101 = 0

以上成功统计出6中设置的位数。

与在每次迭代时右移数字并检查是否设置了最低有效位相比，此优化可帮助您改进算法。在前一种情况下，您在最高有效设置位所在的位置数处进行操作。假设 2 的幂 2^7，你迭代 8 次直到数字变为零。使用优化方法时，您可以根据设置的位数进行迭代。对于 2^7，它只是一次迭代。