Побитовое умножение с коррекцией на переполнение - PullRequest
Новая
       18

Побитовое умножение с коррекцией на переполнение

0 голосов
/ 04 октября 2019

Я пытаюсь использовать побитовые операторы (! ~ & ^ | + << >>) в C, чтобы добиться умножения на 4, а также исправления для положительного и отрицательного переполнения, возвращая значения Max и Minimum соответственно. Например, 

Function(0x10000000) = 0x40000000
Function(0x20000000) = 0x7FFFFFFF
Function(0x80000000) = 0x80000000

Мой основной метод заключается в проверке знака продукта, чтобы найти, ожидали ли он изменения. 

    int funcMultBy4(int x){
        int signedBit=(x>>31);                                                                            
        int minValue= 1<<31;
        int xtimes4= x<<2;
        int maxValue= (x ^ xtimes4) >> 31;
        int saturate= maxValue & (signedBit ^ ~minValue);
        return saturate | (xtimes4 ^ ~maxValue) ;
     }

В настоящее время при умножении 0x7fffffff я получаю -1, ачем ожидалось 0x7FFFFFFF. Я понимаю, что, возможно, где-то необходим сдвиг на 1, но я не могу найти свою ошибку.

1 Ответ

2 голосов
/ 05 октября 2019

Это ^ в последней строке, которое должно быть &, и переполнение должно быть обнаружено как в первом, так и во втором сдвиге битов.

Эта небольшая реорганизация функции кажется более интуитивноймне: 

     int funcMultBy4(int x)
     {
        int signedBit = (x>>31);
        int minValue = 1<<31;
        int xtimes4 = x<<2;
        int overflow = (x ^ (x<<1) | (x ^ (x<<2))) >> 31;
        int saturate = (signedBit ^ ~minValue);
        return (overflow & saturate) | (~overflow & xtimes4) ;
     }

Конечно, код зависит от размера int, который должен быть 32-битным. Вы можете использовать тип фиксированной ширины int32_t или заменить 31 на ((int)((sizeof(int)<<3)-1)) (может быть определено в макросе).

...