30

我理解>>>溢出的修复：当添加两个大的正多头时，你最终可能会得到一个负数。有人能解释一下这种按位移位如何神奇地解决溢出问题吗？和它有什么不同>>？

我的怀疑：我认为这与 Java 使用二进制补码这一事实有关，因此如果我们有额外的空间，溢出是正确的数字，但因为我们没有，所以它变成了负数。因此，当您移位并用零填充时，由于二进制补码，它会神奇地固定。但我可能是错的，有位头脑的人必须确认。:)

4

3 回答 3

54

简而言之，(high + low) >>> 1这是一种使用未使用的符号位对非负数进行正确平均的技巧。

high在和都是非负的假设下low，我们肯定知道最高位（符号位）为零。

所以两者high实际上low都是 31 位整数。

high = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824
low  = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824

当您将它们加在一起时，它们可能会“溢出”到顶部。

high + low =       1000 0000 0000 0000 0000 0000 0000 0000
           =  2147483648 as unsigned 32-bit integer
           = -2147483648 as signed   32-bit integer

(high + low) / 2   = 1100 0000 0000 0000 0000 0000 0000 0000 = -1073741824
(high + low) >>> 1 = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824

  • 作为带符号的 32 位整数，它溢出并翻转为负数。因此(high + low) / 2是错误的，因为high + low可能是负面的。

  • 作为无符号 32 位整数，总和是正确的。所需要的只是将它除以 2。

当然 Java 不支持无符号整数，所以我们最好除以 2（作为无符号整数）是逻辑右移>>>。

在具有无符号整数的语言（例如 C 和 C++）中，它变得更加棘手，因为您的输入可以是完整的 32 位整数。一种解决方案是：low + ((high - low) / 2)

>>>最后列举、>>和之间的区别/：

  • >>>是逻辑右移。它用零填充高位。
  • >>是算术右移。它用原始最高位的副本填充其上部。
  • /是除法。

数学上：

  • x >>> 1将x其视为无符号整数并将其除以 2。它四舍五入。
  • x >> 1将x其视为有符号整数并将其除以 2。它向负无穷大舍入。
  • x / 2将x其视为有符号整数并将其除以 2。它向零舍入。
于 2012-12-09T06:37:42.513 回答
11

它对最高位进行零填充，而不是对它们进行符号填充。

int a = 0x40000000;
(a + a)  /  2 == 0xC0000000;
(a + a) >>> 1 == 0x40000000;
于 2012-12-09T06:25:21.860 回答
5

我建议阅读 Joch Bloch 的http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html#!/2006/06/extra-extra-read- all-about-it-nearly.html关于高低

“我为 JDK 编写的二进制搜索版本包含相同的错误。在等待了 9 年左右之后，它最近破坏了某人的程序，因此向 Sun 报告了该错误。”

于 2012-12-09T07:08:53.473 回答