1

I saw a bunch of codes which can do simple arithmetic operations in constant-time.

But there is a code makes me curious.

Here is a code written in C.

int ct_lt_u32(uint32_t x, uint32_t y){
    return (x^((x^y)|((x-y)^y)))>>31;
}

This function returns 1 if x<y, 0 otherwise.

However, I cannot understand why this function works. Can anyone help me to understand this function? There are only XOR, OR, shift and subtraction.

Serenity
  • 23
  • 2
  • 1
    I am curious to know if this is the underlying implementation of the "less than operator" or is it just something built for fun. – vighnesh153 Jul 26 '23 at 05:08
  • 2
    Remember that if `x < y`, then `x-y` will have the sign bit set. That's all this is doing, plus handling the corner cases for overflow. – Tim Roberts Jul 26 '23 at 05:10

0 Answers0