Побитовая проверка переполнения в c

Question

Я пытаюсь написать две функции, которые будут проверять/предотвращать переполнение в c (используя только! ~ | &^+), но не могу получить его. Первый - это некоторый двойной комплимент/подписанный int, который будет соответствовать количеству бит certatin: fitsB (int x, int n), где int и n - размер используемых битов. Также функция, которая будет проверять, не будет ли два ints не переполняться при добавлении вместе: overflowInt (int x, int y). Я могу получить его, если они являются неподписанными ints, но негативы просто усложняют меня. Кто-нибудь знает, как это сделать?

Там также нет литья и Интс всегда 32 бит

Answer 1

/* 
* addOK - Determine if can compute x+y without overflow 
* Example: addOK(0x80000000,0x80000000) = 0, 
*   addOK(0x80000000,0x70000000) = 1, 
* Legal ops: ! ~ &^| + << >> 
* Max ops: 20 
* Rating: 3 
*/ 
int addOK(int x, int y) { 
    // Find the sign bit in each word 
    //if a and b have different signs, you cannot get overflow. 
    //if they are the same, check that a is different from c and b is different from c, 
    // if they are the same, then there was no overflow. 
    int z=x+y; 
    int a=x>>31; 
    int b=y>>31; 
    int c=z>>31; 
    return !!(a^b)|(!(a^c)&!(b^c)); 
} 

Answer 2

х будет соответствовать в п битов, если х < 2^(N-1).

Вопрос о переполнении нуждается в дополнительной информации. Два ints не будут переполняться, если вы назначите их длинному (или двойному).

Answer 3

Используя приведенный выше пример (Adam Shiemke), вы можете найти максимальное (положительное) значение и минимальное значение (отрицательное), чтобы получить диапазон для n числа бит. 2^(n-1) (из примера Адама) и минус один для максимального/положительного числа, которое может быть представлено в n битах. Для минимального значения отрицаем 2^(n-1), чтобы получить минимальное значение x => - (2^(n-1)); (Обратите внимание на> = not> для минимального диапазона). Например, для n = 4 бит 2^(4-1) - 1 = 2^3 -1 = 7, поэтому x < = 7 и x> = -8 = (- (2^(4-1)).

Это предполагает, что исходный ввод не переполняет 32-битное quanity (надеюсь, что ошибка возникнет в этом состоянии), а количество бит, которое вы используете, меньше 32 (поскольку вы добавляете 1 для отрицательного диапазона, и если вы имеют 32 бита, он будет переполняться, см. ниже пояснение).

Чтобы определить, будет ли добавление переполняться, если у вас есть максимальное значение, значение x + y < =. Используя алгебру, мы можем получить y < = максимальное значение - x. Затем вы можете сравнить переданное значение y и если оно не соответствует условию, добавление будет переполняться. Например, если x является максимальным значением, t hen y < = 0, поэтому y должно быть меньше или равно нулю или добавление будет переполняться.