Runtime Error : 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：未定义行为 prog_joined.cpp:16:44

最后执行的输入：2147483647

Answer 1

TLDR：这是下溢的二进制补码算术问题。

您的错误正确地表明“-2147483648 - 1 无法在 'int' 类型中表示”。整数类型的一些背景知识可能会有所帮助。

整数类型是 four-byte（32 位）数学整数表示。因此它应该能够表示 2^32 -1 个正整数。但是，很快就很明显负整数也需要表示。解决方案是使用最高有效位（MSB：大端排序中最左边的位）作为标志来确定整数将被解释为正数还是负数。将 MSB 设置为 1 会提醒计算机后面的 31 位代表一个负整数，设置为 0 则代表一个正整数。基本上，这称为二进制补码，尽管快速在线搜索会更清楚、更详细地解释它。 As a result the range of the integer type is [-2,147,483,648 to 2,147,483,647] where -2,147,483,648 is represented in binary as 0b10000000000000000000000000000000 and 2,147,483,647 as 0b01111111111111111111111111111111.正如 2,147,483,647 加一会溢出到最大负整数的二进制表示一样，-2,147,483,648 减一也会下溢到最大正整数。

关于你的第二个函数的运行时错误。

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 表示的数字。这会导致下溢错误，从而导致您的计算机引发运行时错误。

N.B。这是我有史以来第一个 Stack 答案，所以如果有人对下次如何更好地回答有任何建议，将不胜感激。

Runtime Error : Integer Overflow for Complement Number Problem

Runtime Error : Integer Overflow for Complement Number Problem

c++

numbers

bit-manipulation