News for hackers. Stuff that matters.
Re:Binary search with confidence by iib on Monday March 07, 2022 @06:34AM (#30586557)
I think that may actually be considered buggy, and the actual definition should be

   long add(int x, int y) { return x + y; }
with the caveat of course that `long` is larger than an `int`, which I can't recall if it is valid on all platforms. So mathematical u32 + u32 should be u64, but you can define an `add` function that has strict overflow behavior.
Re:Binary search with confidence by tromp on Monday March 07, 2022 @06:39AM (#30586589)
Shouldn't you write

    return (long)x + y;
to ensure the addition happens after the conversion to long?
Re:Binary search with confidence by rustybolt on Monday March 07, 2022 @06:43AM (#30586613)
Yes, this is essentially the case I'm making: if this implementation of binary search is buggy, then so is the addition operator in C (and many related languages).
Re:Binary search with confidence by cxr on Friday March 11, 2022 @03:07PM (#30645350)
They're not comparable. Trying to compare them suggests that you don't understand what the issue is with the `(low + high) / 2` case, or you don't want to acknowledge it.

Simple addition will fail if the result of the expression should fall outside the range of integers expressible for a given integer width—because it can't fit. That's not insightful. It's facile. The criticism of the naive midpoint computation is not facile.

The problem with using `(low + high) / 2` to compute the midpoint (instead of `(high - low) / 2 + low`) is that it will give invalid results even when the data type from the signature is wide enough that the expected result can fit.

Re:Binary search with confidence by thfuran on Monday March 07, 2022 @08:53AM (#30587747)
No, it's just slightly unintuitive. That's not the same thing.
Re:Binary search with confidence by ufo on Monday March 07, 2022 @09:41AM (#30588356)
That might not be enough. On 64-bit linux, both int and long are 32 bits.
Re:Binary search with confidence by adrian_b on Monday March 07, 2022 @11:09AM (#30589474)
You meant on 64-bit Windows.

On most 64-bit UNIX-like systems, long is the same with long long.

Re:Binary search with confidence by mark-r on Monday March 07, 2022 @01:58PM (#30591844)
Microsoft are the kings of backward compatibility. Since long has been 32 bits for the last 20 years, it shall remain so until the end of time. Linux compilers are free to be a little more pragmatic. The standards are flexible enough to allow either behavior.
Re:Binary search with confidence by mark-r on Monday March 07, 2022 @11:15AM (#30589551)
In Microsoft C++ long and int are both the same size, 32 bits. Even when size_t is 64 bits.