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 行:Char 44:运行时错误:有符号整数溢出:-2147483648 - 1 无法以“int”类型表示(solution.cpp) 摘要:UndefinedBehaviorSanitizer:未定义行为 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 以二进制表示为 0b10000000000000000000000000000000，2,147,483,647 以二进制表示为 0b011111111 11111111111111111111111。正如 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 上回答，所以如果有人对下次如何更好地回答有建议，我将不胜感激。