Проверка переполнения в сложении чисел

Question

Требуется вернуть 1, если переполнение после сложения чисел x и y не произошло, иначе 0.

Использовать можно только битовые операции: ! ~ & ^ | + << >>.
if, for использовать нельзя.

Программа проходит не все тесты:

int addOK(int x, int y)        
{
    return (!(((x + y) >> 31) & 1)) & ((!(x >> 31)) & 1)  & ((!(y >> 31)) & 1);
}

Как исправить ошибки в коде?

Answer 1

Вроде бы так:

!((a^b)&0x80000000)&!!(((a+b)^(a&b))&0x80000000)
!((a^b)&0x80000000)&!(((a+b)^~(a&b))&0x80000000)
!(((a^b)|((a+b)^~(a&b)))&0x80000000)

Проверка:

for (var f of [
  (a,b)=>!((a^b)&0x80000000)&!!(((a+b)^(a&b))&0x80000000),
  (a,b)=>!((a^b)&0x80000000)&!(((a+b)^~(a&b))&0x80000000),
  (a,b)=>!(((a^b)|((a+b)^~(a&b)))&0x80000000),
]) {
  console.log([[0,0], [100,1000], [-100,1000], [-100,1000], [-100,-1000], [2**30,2**30-1], [-(2**30),-(2**30)], [2**30,2**30], [2**30+8,2**30-2]].map(a=>+f(...a))+"")
}

Хотя и не соответствует стандарту, сначала сложить, а потом проверять.

Answer 2

Вроде бы такое должно работать:

int test(int a, int b)
{
    return ((((a+b)^a)&((a+b)^b))>>31)&1;
}

По крайней мере, тесты от Qwertiy проходит :)

Не используя явное x+y -

int test(int x, int y)
{
    return (((~(x^y)&0x80000000)&~(((x^(~(x^y)&0x80000000))+y)^y))>>31)&1;
}

Скобок мог и лишних навертеть :))

Во что это превратил VC++2017:

; 22   :     return (((~(x^y)&0x80000000)&~(((x^(~(x^y)&0x80000000))+y)^y))>>31)&1;

    mov ecx, edi
    xor ecx, esi
    not ecx
    mov edx, ecx
    shr ecx, 31
    and edx, -2147483648            ; 80000000H
    xor edx, edi
    add edx, esi
    xor edx, esi
    not edx
    shr edx, 31
    and edx, ecx

Так что - исходя из действий оптимизатора - можно так:

return (~(((~(x^y)&0x80000000^x)+y)^y)>>31) & (~(x^y) >> 31);

БЛОГ НА HUSL

Проверка переполнения в сложении чисел

Ответы (2 шт):