арифметика c сдвиг вправо в 0 с, когда MSB равен 1 - PullRequest
Новая
       98

арифметика c сдвиг вправо в 0 с, когда MSB равен 1

0 голосов
/ 09 января 2020

В качестве упражнения я должен написать следующую функцию:
умножить x на 2, насыщать до Tmin / Tmax при переполнении, используя только побитовые и битовые операции сдвига.
Теперь это мой код: 

// xor MSB and 2nd MSB. if diferent, we have an overflow and SHOULD get 0xFFFFFFFF. otherwise we get 0.
int overflowmask = ((x & 0x80000000) ^ ((x & 0x40000000)<<1)) >>31;
                                                             // ^ this arithmetic bit shift seems to be wrong
// this gets you Tmin if x < 0 or Tmax if x >= 0
int overflowreplace = ((x>>31)^0x7FFFFFFF);

// if overflow, return x*2, otherwise overflowreplace
return ((x<<1) & ~overflowmask)|(overflowreplace & overflowmask);

теперь, когда overflowmask должно быть 0xFFFFFFFF, вместо этого оно равно 1, что означает, что арифметическое c битовое смещение >>31 сместилось в 0 с вместо 1 с (MSB получил XORed к 1 , затем смещено вниз).
x подписано и MSB равно 1, поэтому согласно C99 арифметическое c смещение вправо должно заполняться 1 с. Чего мне не хватает?

РЕДАКТИРОВАТЬ: Я только что догадался, что этот код не является правильным. Чтобы обнаружить переполнение, достаточно, чтобы 2-й MSB был равен 1.
Однако мне все еще интересно, почему сдвиг битов заполняется 0 с.

РЕДАКТИРОВАТЬ:
Пример: x = 0xA0000000 

x & 0x80000000 = 0x80000000 
x & 0x40000000 = 0 
XOR => 0x80000000 
>>31 => 0x00000001

РЕДАКТИРОВАТЬ:
Решение: 

int msb = x & 0x80000000;
int msb2 = (x & 0x40000000) <<1;
int overflowmask = (msb2 | (msb^msb2)) >>31;
int overflowreplace = (x >>31) ^ 0x7FFFFFFF;
return ((x<<1) & ~overflowmask) | (overflowreplace & overflowmask);

Ответы [ 3 ]

3 голосов
/ 09 января 2020

Даже на машинах с двумя дополнениями поведение правого сдвига (>>) для отрицательных операндов определяется реализацией.

Более безопасный подход - работать с типами без знака и явно ИЛИ в MSB.

Пока вы занимаетесь этим, вы, вероятно, также захотите использовать типы фиксированной ширины (например, uint32_t), а не работать на платформах, которые не соответствуют вашим ожиданиям.

1 голос
/ 09 января 2020

Никогда не используйте побитовые операнды в знаковых типах. В случае сдвига вправо для целых чисел со знаком, компилятор может получить арифметику c или логический сдвиг.

Это только одна из ваших проблем. Когда вы используете шестнадцатеричную целочисленную константу 0x80000000, она на самом деле имеет тип unsigned int , как описано здесь . Это случайно превращает все ваше выражение (x & 0x80000000) ^ ... в тип без знака из-за целочисленного правила продвижения , известного как "обычные арифметические c преобразования". Принимая во внимание, что выражение 0x40000000 подписано int и работает так, как ожидалось (компилятор спецификаций c).

Решение:

  • Все задействованные переменные должны иметь тип uint32_t.
  • Все участвующие шестнадцатеричные константы должны иметь суффикс u.
  • Чтобы получить что-то арифметическое c сдвиг переносимым, вам придется сделать
    (x >> n) | (0xFFFFFFFFu << (32-n)) или что-то подобное взломать .
1 голос
/ 09 января 2020

0x80000000 рассматривается как число без знака, что приводит к преобразованию всего в беззнаковое. Вы можете сделать это: 

// xor MSB and 2nd MSB. if diferent, we have an overflow and SHOULD get 0xFFFFFFFF. otherwise we get 0.
int overflowmask = ((x & (0x40000000 << 1)) ^ ((x & 0x40000000)<<1)) >>31;

// this gets you Tmin if x < 0 or Tmax if x >= 0
int overflowreplace = ((x>>31)^0x7FFFFFFF);

// if overflow, return x*2, otherwise overflowreplace
return ((x<<1) & ~overflowmask)|(overflowreplace & overflowmask);

ИЛИ записать константы в отрицательных десятичных числах

ИЛИ будет хранить все константы в переменных const int, чтобы гарантировать их подпись.

...