This is my go-to implementation, but I make one little tweak. It’s very unlikely that you will overflow a long, but you can you guarantee that you’ll avoid overflow like this:
It explicitly uses the carry flag from the addition as the top bit of the right-rotated result.
Not super useful for anything other than averaging two uints but that's x86 for you.
What I missed in my first pass was
* Forgetting exactly which register was the low index and which was the high index
* Underflow if array size was zero from setting the last index to (size - 1)
That's my C# implementation, so long is 64 bits and int is 32 bits. 64 bits will never overflow in my lifetime. That's basically a Google scale amount of data.
There is an implicit invariant that 0 <= min, and min <= max, so max - min is between 0 and int_max inclusive, so you avoid overflowing with that calculation. To be sure that you avoid overflowing at the sum step, you need to prove that min + (max - min) / 2 <= max.
what if max is already overflown due to size of array (without even doing the lo + high calculation?) Then
min + (max- min)/2 would be min + (smaller negative value) which would violate the min + (max-min)/2 <= max
add rax, rbx
rcr rax, 1
It explicitly uses the carry flag from the addition as the top bit of the right-rotated result.
Not super useful for anything other than averaging two uints but that's x86 for you.
What I missed in my first pass was