To explain: The rcr instruction performs a right rotation and shifts the CF (carry flag) bit into the most significant position. Together with the preceding add instruction, this effectively provides an n+1 bit operation on n-bit registers.

This is correct for unsigned integers, but incorrect for signed.

For x=INT_MIN+1 (0b1000...1) y=INT_MAX (0b01111...1) this gives INT_MIN (0b1000...0) instead of 0.

You are correct, however most binary search algorithms wouldn't need negative numbers.

It is, however, the exact case shown in the linked article. "Let us say that I ask you to find the number I am thinking about between -1000 and 1000, by repeatedly guessing a number."

You don't need a negative number to solve that fyi.

If the correct number is -300 you might

No, because in the context of a binary search you should be able to map everything to a positive integer. So if your question is "find the midpoint, so I can start searching there" your "midpoint" is not going to be a negative number in the context of binary search.

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.

> No, because in the context of a binary search you should be able to map everything to a positive integer. So if your question is "find the midpoint, so I can start searching there" your "midpoint" is not going to be a negative number in the context of binary search.

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.

It is being pedantic, but the issue is in the context of binary search:

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.

It's a bit of a shame that programming languages above assembly don't expose the flag bits. Would be an interesting feature to explore for a "medium level language".

I believe that the reason is that high-level programming languages are meant to run on different types of CPUs and the flag implementations are different in different CPUs.

Have a look at https://github.com/wiz-lang/wiz. I agree that this in an unexplored area.

For a higher level language, one idea would be to automatically widen the result of operations, so for example adding two 32 bit integers would have a 33 bit result.

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"?

ChatGPT came up with this solution when I asked it to handle the overflow, and then asked it to be more efficient.

  // 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;
  }

Yes, but that converts to 128 bits before doing the actual sum (maybe the compiler can still optimize that away?)

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 knows better!

> 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

But all of these use a bit shift instead of the (I)DIV instruction. I wasn't saying compilers can't be stupid, but the AI-generated comment explicitly stated that the shift operation was more efficient than division, not that it would result in fewer instructions emitted.

    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)