c++ - 运行时错误 : Integer Overflow for Complement Number Problem

Question

我有 3 种补充给定二进制数的方法。第一种和第三种方法不会出现任何整数溢出错误。你能解释一下为什么第二种方法会出现这个运行时错误吗？
这是代码:

 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 行:字符 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 则代表正整数。基本上，这被称为二进制补码，尽管快速在线搜索会更清楚和详细地解释它。因此，整数类型的范围是 [-2,147,483,648 到 2,147,483,647]，其中 -2,147,483,648 用二进制表示为 0b100000000000000000000000000000000000000000000000000000000000000000000000001611111111111111111111111111111111111111111111111111111111111111111111111111111111111111110正如在 2,147,483,647 上加 1 会溢出到最大负整数的二进制表示中一样，从 -2,147,483,648 中减去 1 也会下溢到最大正整数。
关于第二个函数中的运行时错误。

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为2,147,483,647，变量n被赋值为31(floor(30.9999999993 + 1)，去掉多余的分号就好了。因此num_with_all_ones被赋值为1后跟31 0(或者正如我们在上面看到的，最大负整数 -2147483648) 和 1。这会导致下溢错误，从而导致您的计算机引发运行时错误。
注意这是我有史以来的第一个 Stack 答案，所以如果有人对下次如何更好地回答有建议，那将不胜感激。