5 ms·

add x,y rcr x,1

adwn 4y ago
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.
flohofwoe 4y ago
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".
- gdprrrr 4y ago
  Have a look at https://github.com/wiz-lang/wiz https://github.com/wiz-lang/wiz. I agree that this in an unexplored area.
- distcs 4y ago
  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.
- rep_lodsb 4y ago
  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"?
  - flerchin 4y ago
    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; }
    - rep_lodsb 4y ago
      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.
      - jlokier 4y ago
        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
deleted 4y ago
[deleted]
planede 4y ago
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.
- rep_lodsb 4y ago
  You are correct, however most binary search algorithms wouldn't need negative numbers.
  - IncRnd 4y ago
    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."
    - roflyear 4y ago
      You don't need a negative number to solve that fyi.
      - anonymoushn 4y ago
        If the correct number is -300 you might
        roflyear 4y ago
        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.
        IncRnd 4y ago

add x,y rcr x,1

adwn 4y ago

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.

flohofwoe 4y ago

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

gdprrrr 4y ago
Have a look at https://github.com/wiz-lang/wiz https://github.com/wiz-lang/wiz. I agree that this in an unexplored area.
distcs 4y ago
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.
rep_lodsb 4y ago
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"?
- flerchin 4y ago
  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; }
  - rep_lodsb 4y ago
    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.
    - jlokier 4y ago
      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

deleted 4y ago

[deleted]

planede 4y ago

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.

rep_lodsb 4y ago
You are correct, however most binary search algorithms wouldn't need negative numbers.
- IncRnd 4y ago
  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."
  - roflyear 4y ago
    You don't need a negative number to solve that fyi.
    - anonymoushn 4y ago
      If the correct number is -300 you might
      - roflyear 4y ago
        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.
        IncRnd 4y ago