News for hackers. Stuff that matters.
Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by dunhuang_nomad on Sunday November 06, 2022 @10:05AM (#33493352)
Does anyone know why the bitshift method works?

Is it that low and high are both floating point, so you're not constrained by int precision and so you don't get an overflow error. The article makes it sound like sign switching is the issue, but this is just a general overflow problem, right?

Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by odo1242 on Sunday November 06, 2022 @10:39AM (#33493715)
No, it's because the reason that integers overflow is that negative numbers are technically stored as larger than positive numbers in the Two's complement representation most computers use to store integers. Neither low and high are floats.

Example with 8-bit integers (from wikipedia):

Bits, Unsigned value, Signed value

0000 0000, 0, 0

0000 0001, 1, 1

0000 0010, 2, 2

0111 1110, 126, 126

0111 1111, 127, 127

1000 0000, 128, −128

When the logical bit shift is conducted on -128, -128 is treated as an unsigned integer. Its sign bit gets shifted such that the integer becomes 0100 0000, aka 64.

Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by dunhuang_nomad on Sunday November 06, 2022 @11:53AM (#33494557)
Oh I see, this is very helpful. Thank you.
Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by dataflow on Sunday November 06, 2022 @10:06AM (#33493359)
The ">>>" operator works, the ">>" operator doesn't. The reason the former works is that it basically performs unsigned division by a power of 2; the latter does it signed. There's no floating-point.
Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by erikpukinskis on Sunday November 06, 2022 @10:18AM (#33493503)
What do the five >s and the , mean in this comment?
Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by dataflow on Sunday November 06, 2022 @10:28AM (#33493615)
>>> is bitwise right shift (fills in with zeros), >> is arithmetic right shift (fills in with the sign bit).
Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by a1369209993 on Sunday November 06, 2022 @04:23PM (#33497352)
> >>> is bitwise right shift

Well, they're both bitwise right shifts, the ">>>" is specifically a logical or unsigned right shift.

Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by dataflow on Sunday November 06, 2022 @05:52PM (#33498396)
Whoops yes I meant logical.