(operand1 < operand2) || (~操作数1<进位)的结果

Question

我正在尝试理解下面代码的逻辑，这些代码添加了一个进位：

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

打印

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

如果

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

(operand1 < operand2) || (~operand1 < carry)怎么可能是0？0||1 = 1。

此外，这看起来像是一些进位操作。在这里，~operand1和carry有什么关系？

Answer 1

std::cout << "(~operand1 < carry): " << (~operand1 < carry) << std::endl;

与函数的功能不匹配。试一试

std::cout << "(~sum < carry): " << (~(operand1+operand2) < carry) << std::endl;，对于其他比较也是如此，因为operand1实际上应该是总和。

Answer 2

这看起来像是任意精度加法的一部分。它接受三个输入，返回两个输出。输入是任意精度数字(operand1和operand2)的两个匹配字和来自上一次(低位字)运算的进位。它返回可能已经溢出的和和新进位。

在计算总和溢出时，有两个与operand1 + operand2 + carry相加的机会，这两个机会对应于所讨论的操作((operand1 < operand2) || (~operand1 < carry))的两个部分。

第一次加法是作为operand1 += operand2执行的，因此第一次检查operand1 < operand2相当于检查和是否小于其中一个加数- operand1现在存储和。当且仅当操作溢出时，才会发生这种情况(添加两个没有溢出的非负数不能使结果更小，但执行溢出总是会使结果更小，因为它有效地将x- 2^n相加，其中x< 2^n)。第二个添加本可以用同样的方式进行检查，但没有。

检查的第二部分，~operand1 < carry，改为主动工作。诀窍是使用~operand1来计算2**64 - operand1 - 1 (记住，由于模运算，2**64和0是相同的数字)。将表达式编写为0 - operand1 - 1 < carry时，表达式会变得更容易理解，然后可以简化为0 - operand1 <= carry。由于2**64 - operand1显然是需要添加到operand1中才能实现溢出的数字，因此将其与carry进行比较应该更有意义。