bit-manipulation - 使用位操作来计算两个数字的平均值？

Question

我找到了这段代码:

int mid = (l & r) + ((l ^ r) >> 1)

与mid=(l+r)/2相同

但我不明白为什么？

有什么帮助吗？谢谢!

Answer 1

不完全相同，重点是不一样。它大部分是相同的，但没有溢出问题:如果你输入两个正数，结果永远不会是负数。 mid = (l + r)/2 则不然，如果您有 l = 0x7fffffff, r = 1 ，那么真正的中点是 0x40000000 但简单的中点计算表明它是 0xc0000000，一个很大的负数。

加法可以分解为:

x + y = (x ^ y) + ((x & y) << 1)

这只是一个简单的“计算每位数字和，然后分别应用进位”分解。然后将整个内容右移 1，同时恢复“从末尾掉落”的位，方法是一开始不向左移动，而将其他内容向右移动，

x + y = ((x ^ y) >> 1) + (x & y)

这是中点计算。请注意，它向下舍入，而不是向零舍入，这对于负面结果很重要。我不会称结果错误，它仍然位于端点之间的中间，但它与正常有符号除以2的结果不匹配(通常四舍五入到零，尽管关于它应该如何舍入的意见不同)。

您可以通过使用无符号右移将其更改为适用于所有无符号整数:

// unsigned midpoint without wrapping/overflow
int mid = (l & r) + ((l ^ r) >>> 1);

当然，作为无符号中点，负输入被隐式地视为非常大的正数，这就是重点。

如果您使用有符号但非负数(通常是中点计算的情况)，则可以使用明显更简单的方法

int mid = (x + y) >>> 1