C проверка на переполнение во время вычитания - PullRequest
Новая
       49

C проверка на переполнение во время вычитания

0 голосов
/ 17 октября 2018

Я пытался определить, есть ли переполнение при вычитании двух чисел из 32 бит.Мне дали следующие правила: 

Can only use: ! ~ & ^ | + << >>
 *   Max uses: 20
Example: subCheck(0x80000000,0x80000000) = 1,
 *       subCheck(0x80000000,0x70000000) = 0
No conditionals, loops, additional functions, or casting

Пока у меня есть 

int dif = x - y; // dif is x - y
int sX = x >> 31; // get the sign of x
int sY = y >> 31; // get the sign of y
int sDif = dif >> 31; // get the sign of the difference
return (((!!sX) & (!!sY)) | (!sY)); // if the sign of x and the sign of y 
                                    // are the same, no overflow. If y is 
                                    // 0, no overflow.

Теперь я понимаю, что не могу использовать вычитание в реальной функции (-), поэтому вся моя функция бесполезнав любом случае.Как я могу использовать метод, отличный от вычитания, и определить, есть ли переполнение, используя только побитовые операции?

Ответы [ 2 ]

0 голосов
/ 18 октября 2018

Спасибо всем за помощь!Вот что я придумала, чтобы решить мою проблему: 

int ny = 1 + ~y; // -y
int dif = x + ny; // dif is x - y
int sX = x >> 31; // get the sign of x
int sY = y >> 31; // get the sign of -y
int sDif = dif >> 31; // get the sign of the difference
return (!(sX ^ sY) | !(sDif ^ sX));

Каждый случай, с которым я пытался, работал.Я изменил то, что предложил @HackerBoss, получив знак y, а не ny, а затем поменяв две проверки в операторе return.Таким образом, если знаки совпадают или знак результата и знак x совпадают, возвращается значение true.

0 голосов
/ 17 октября 2018

Чтобы избежать неопределенного поведения, я буду предполагать, что целые числа представлены в виде дополнения до двух, исходя из ваших вычислений sX, sY и sDif.Я также предполагаю, что sizeof(int) равно 4. Вероятно, было бы лучше использовать int32_t, если вы работаете только с 32-разрядными целыми числами, поскольку размер int может варьироваться в зависимости от платформы.

Поскольку вам разрешено использовать сложение, вы можете рассматривать вычитание как сложение отрицания числа.Число, хранящееся в дополнении к двум, можно отменить, перевернув все биты и добавив один.Это дает следующий модифицированный код: 

int ny = 1 + ~y; // -y
int dif = x + ny; // dif is x - y
int sX = x >> 31; // get the sign of x
int sNY = ny >> 31; // get the sign of -y
int sDif = dif >> 31; // get the sign of the difference
return ((sX ^ sNY) | (~sDif ^ sX)); // if the sign of x and the sign of y 
                                    // are the same, no overflow. If the
                                    // sign of dif is the same as the signs
                                    // of x and -y, no overflow.
...