add x,y
rcr x,1 add x,y
rcr x,1For x=INT_MIN+1 (0b1000...1) y=INT_MAX (0b01111...1) this gives INT_MIN (0b1000...0) instead of 0.
I think in the unfortunate example question the binary search is from -1000 to +1000, but the question is not about binary search, it is about finding the midpoint between two numbers.
That's not true. Binary search doesn't map everything to a positive integer. You are incorrectly looking at the index offset, but the issue is determining the midpoint between two signed numbers.
Let us say that I ask you to find the number I am thinking about between -1000 and 1000, by repeatedly guessing a number. With each guess, I tell you whether your guess is correct, smaller or larger than my number. A binary search algorithm tries to find a value in an interval by repeating finding the midpoint, using smaller and smaller intervals. You might start with 0, then use either -500 or 500 and so forth.
You don't need negative numbers to do this.... you can easily do it with only positive numbers.
Since the expression will be eventually assigned to some variable or passed as a function parameter, it will have a limited range (and there should be an exception if that overflows), but intermediate results could be larger.
Is this just completely unfeasible, or just not done because "that's not how C does it"?
// Calculates the midpoint of two 64-bit integers
// and returns the result as a 64-bit integer.
int64_t midpoint(int64_t a, int64_t b) {
// Use the __int128 type to calculate the sum
// of the two input numbers without overflowing.
__int128 sum = (__int128) a + (__int128) b;
// Shift the sum to the right by 1 bit to divide it by 2
// and get the midpoint. This operation is equivalent to
// sum / 2, but is more efficient because it uses a bit shift
// operation instead of a division operation.
int64_t midpoint = (int64_t) (sum >> 1);
return midpoint;
}My idea was a better language where typecasts are never needed at all, because the compiler knows how the result will be used (in this example, returned as int64_t), and can produce whatever code is most efficient and either produces the correct result or a runtime exception.
edit: Also any non-toy compiler will optimize division by powers of two into a shift operation, so ChatGPT isn't being clever at all here, just repeating a common superstition.
> ChatGPT isn't being clever at all here, just repeating a common superstition
Source:
#include <stdint.h>
int64_t midpoint_ChatGPT(int64_t a, int64_t b) {
__int128 sum = (__int128) a + (__int128) b;
// Shift the sum to the right by 1 bit to divide it by 2
// and get the midpoint. This operation is equivalent to
// sum / 2, but is more efficient because it uses a bit shift
// operation instead of a division operation.
int64_t midpoint = (int64_t) (sum >> 1);
return midpoint;
}
int64_t midpoint_rep_lodsb(int64_t a, int64_t b) {
__int128 sum = (__int128) a + (__int128) b;
// Shifts are for the superstitious.
int64_t midpoint = (int64_t) (sum / 2);
return midpoint;
}
Clang -O2 output: _midpoint_ChatGPT:
pushq %rbp
movq %rsp, %rbp
movq %rdi, %rcx
sarq $63, %rcx
movq %rsi, %rax
sarq $63, %rax
addq %rdi, %rsi
adcq %rcx, %rax
shldq $63, %rsi, %rax
popq %rbp
retq
_midpoint_rep_lodsb:
pushq %rbp
movq %rsp, %rbp
movq %rdi, %rcx
sarq $63, %rcx
movq %rsi, %rax
sarq $63, %rax
addq %rdi, %rsi
adcq %rcx, %rax
movq %rax, %rcx
shrq $63, %rcx
addq %rsi, %rcx
adcq $0, %rax
shldq $63, %rcx, %rax
popq %rbp
retq
GCC -O2 output: midpoint_ChatGPT:
endbr64
movq %rsi, %r8
movq %rdi, %rax
sarq $63, %rdi
sarq $63, %rsi
movq %rdi, %rdx
addq %r8, %rax
adcq %rsi, %rdx
shrdq $1, %rdx, %rax
ret
midpoint_rep_lodsb:
endbr64
movq %rsi, %rcx
movq %rdi, %rax
sarq $63, %rdi
sarq $63, %rcx
movq %rdi, %rdx
addq %rax, %rsi
movq %rcx, %rdi
adcq %rdx, %rdi
xorl %edx, %edx
movq %rdi, %rcx
shrq $63, %rcx
movq %rcx, %rax
addq %rsi, %rax
adcq %rdi, %rdx
shrdq $1, %rdx, %rax
ret midpoint_rep_lodsb_handwritten:
endbr64
movq $0x8000000000000000, %rax
xorq %rax, %rsi ;convert two's complement to biased
xorq %rax, %rdi
addq %rsi, %rdi
rcrq $1, %rdi
xorq %rdi, %rax ;convert back
ret
(sorry if I got the syntax wrong, AT&T is just horrible)