Создайте метод, который проверяет, не переполнится ли x + y с помощью побитовых операций

Мне нужно создать метод на C с использованием побитовых операций, который проверяет, будет ли x + y переполняться или нет. Я могу использовать максимум 20 из следующих операций; ! ~ & ^ | + ‹‹ >> Имейте в виду, что я должен проверять как отрицательные, так и положительные числа.

Я несколько раз пытался заставить его работать. Верна ли моя логика? Я исхожу: если (x + y) меньше x, то он переполнился. Основываясь на этой логике, я написал это;

int addOK(int x, int y)
{
  int sum = x + y;
  int nx = ((~x) + 1);
  int check = (sum + nx)>>31;
  return !check;
}

Благодарю вас!


c methods overflow addition bit-manipulation
person Guambler    schedule 14.04.2012    source источник
comment
К сожалению, переполнение целого числа со знаком приводит к неопределенному поведению. Следовательно, в вашей функции у вас нет контроля над тем, что хранится в sum, и поэтому ваша проверка не очень четко определена.   -  person Joshua Green    schedule 14.04.2012
comment
@guambler ... что произойдет, если вы добавите -128 и 127? 8-bit конечно., твоя логика не подведет, я думаю..! любой способ справиться с этим?   -  person noufal    schedule 29.05.2013

Ответы (1)


arrow_upward
0
arrow_downward

Это должно работать, но он не использует только побитовый оператор, а работает для signed :

int addOK(int x, int y)
{
  int check;
  if (greaterThan(0, x^y)) 
    check = 0; 
  else if (greaterThan(x, 0)) 
    check = greaterThan(y, INT_MAX -x);
  else 
    check = greaterThan(INT_MIN -x, y);

  return check;
}

int greaterThan(int first, int second) {
   /* first > second means second - first is less than 0
      shift the sign bit and then compare it to 1 */
   return (second + (~first +1)) >> ((sizeof(int) * 8) -1) & 1;
}

Если два числа оба положительные, должно быть достаточно:

int addOK(int x, int y) {
 if(x^y < 0)
   return 0;

 return 1;
}
person aleroot    schedule 14.04.2012
comment
это похоже на здравую логику, я попытаюсь преобразовать ее в побитовую - person Guambler; 14.04.2012
comment
Взгляните на мой обновленный ответ, теперь он реализован более побитовым способом... - person aleroot; 14.04.2012