Result of (operand1 < operand2) || (~operand1

I'm trying to understand the logic of the code below that adds with a carry:

#include <iostream>

using namespace std;

inline unsigned char add_uint64_generic(uint64_t operand1, uint64_t operand2, unsigned char carry, unsigned long long *result)
{
    operand1  = operand2;
    *result = operand1   carry;
    return (operand1 < operand2) || (~operand1 < carry);
}

int main()
{
    uint64_t operand1 = 10000;
    uint64_t operand2 = 2000;
    char carry = 255;
    unsigned long long r;
    std::cout << "operand1 < operand2: " << (operand1 < operand2) << std::endl;
    std::cout << "(~operand1 < carry): " << (~operand1 < carry) << std::endl;
    cout<<(int) add_uint64_generic(operand1,operand2,carry,&r) << std::endl;
    cout<< r;
    return 0;
}

prints

operand1 < operand2: 0
(~operand1 < carry): 1
0
12255

operand1 < operand2: 0
(~operand1 < carry): 1

how can (operand1 < operand2) || (~operand1 < carry) be 0? 0||1 = 1.

Also, this looks like some carry operation. What does ~operand1 have to do with carry here?

CodePudding user response：

std::cout << "(~operand1 < carry): " << (~operand1 < carry) << std::endl;
doesn't match what the function does. Try

std::cout << "(~sum < carry): " << (~(operand1 operand2) < carry) << std::endl; and likewise for the other comparison, as operand1 should really be the sum.

CodePudding user response：

This looks like part of a arbitrary precision addition. It takes three inputs and returns two outputs. The inputs are the two matching words of the arbitrary precision numbers (operand1 and operand2) and a carry from the previous (lower word) operation. It returns the sum, which may have overflown and the new carry.

As the sum operand1 operand2 carry is computed, there are two opportunities for the addition to overflow, which correspond to the two halves of the operation in question ((operand1 < operand2) || (~operand1 < carry)).

The first addition is performed as operand1 = operand2, so the first check operand1 < operand2 is equivalent to checking if the sum is smaller than one of the addends - operand1 now stores the sum. This happens if and only if the operation overflowed (adding two non-negative numbers w/o overflow cannot make the result smaller, but performing an overflow will always make it smaller, as it effectively adds x - 2^n where x < 2^n). The second addition could have been checked the same way, but is not.

The second part of the check, ~operand1 < carry, works proactively instead. The trick is the use of ~operand1 to compute 2**64 - operand1 - 1 (remember that 2**64 and 0 are the same number due to modular arithmetic). The expression becomes a bit easier to understand when written as 0 - operand1 - 1 < carry which can then be simplified to 0 - operand1 <= carry. As 2**64 - operand1 is obviously the number that needs to be added to operand1 to achieve overflow, comparing it to carry should make more sense.