Ошибка выполнения: целочисленное переполнение для проблемы с дополнительным числом - PullRequest
Новая
       60

Ошибка выполнения: целочисленное переполнение для проблемы с дополнительным числом

2 голосов
/ 06 мая 2020

У меня есть 3 способа дополнения заданного двоичного числа. 1-й и 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 не может быть представлено в type 'int' (solution. cpp) РЕЗЮМЕ: UndefinedBehaviorSanitizer: undefined-behavior prog_joined. cpp: 16: 44

Последний выполненный ввод: 2147483647

1 Ответ

2 голосов
/ 23 августа 2020

TL; DR: это проблема недостаточного заполнения с арифметикой дополнения до двух.

Ваша ошибка правильно показывает, что «-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 как 0b011111111111111111111111111111. Так же, как добавление единицы к 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 как 2 147 483 647 переменной n присваивается 31 (пол (30.9999999993 + 1), и было бы хорошо удалить лишнюю точку с запятой. Поэтому num_with_all_ones присваивается разница между двоичным числом представлен 1, за которым следует 31 0 (или, как мы видели выше, максимальное отрицательное целое число -2147483648) и единица. Это приводит к ошибке недостаточного заполнения, из-за которой ваш компьютер вызывает ошибку времени выполнения.

NB Это это мой первый ответ на стек, поэтому, если у кого-нибудь есть совет, как лучше ответить в следующий раз, я буду очень признателен.

...