运行时错误：补码问题的整数溢出

Question

我有三种方法来补充给定的二进制数。第一

 int findComplement1(int num) {
        if(num==0)
            return 1;

        int n=num;
        int bit=1;
        while(n>0)
        {
         num=num^bit;
         n/=2;
         bit=bit<<1;
        }
        return num;
    }

//Got Integer Overflow
int findComplement2(int num)
{
    int n = floor(log2(num)+1);;
    int num_with_all_ones =(int) (1<<n)-1;
    return (num_with_all_ones^num);
}

int findComplement3(int num)
{
    if(num==0)
        return 1;
    int result=0;
    int power=1;
    while(num>0)
    {
        int pop=num%2;
        int c=(num%2)^1;
        result+=c*power;
        power=power<<1;
        num=num>>1;
    }
    return result;
}

这是错误消息：运行时错误消息：第7行：Char 44：运行时错误：有符号整数溢出：-2147483648-1不能在类型“int”（solution.cpp）中表示摘要：UndefinedBehaviorSanitizer:undefined behavior prog_joined。cpp:16:44

最后执行的输入：2147483647

Answer 1

TLDR：这是一个下限溢位的二补码算术问题。

您的错误正确地表明“-2147483648-1不能用“int”类型表示。稍微了解一下整数类型可能会有所帮助。

整数类型是数学整数的四字节（32位）表示形式。因此，它应该能够表示2^32-1个正整数。然而，很快就发现，负整数也需要表示。解决方案是使用最高有效位（MSB：在大端排序中最左边的位）作为标志，以确定整数将被解释为正还是负。如果将MSB设置为1，则会提醒计算机，后面的31位表示负整数，如果设置为0，则表示正整数。基本上，这被称为二的补充，尽管快速的在线搜索会更清楚、更详细地解释它。因此，整数类型的范围是[-2147483648到2147483647]，其中-2147483648在二进制中表示为0B10000000000000000000，2147483647表示为0B01111111111111111111。正如向2147483647中添加一会溢出到最大负整数的二进制表示中一样，从-2147483648中减去一也会溢出到最大正整数。

关于您在第二个函数中的运行时错误。

int findComplement2(int num){

    int n = floor(log2(num)+1);;            
    int num_with_all_ones =(int) (1<<n)-1;
    return (num_with_all_ones^num);
}
findComplement2(2147483647);

参数num为2147483647时，变量n被赋值为31（floor（30.9999999993 1），最好删除多余的分号。因此，num_with_all_one被分配一个二进制数和一个二进制数之间的差，二进制数由1后跟31 0表示（或者正如我们前面看到的，最大负整数-2147483648）。这会导致下溢错误，从而导致计算机引发运行时错误。

注意：这是我有史以来的第一个堆栈答案，所以如果有人对下次如何回答更好有建议，我将不胜感激。