пятница, 12 марта 2010 г.

Арифиметический и логический сдвиг

О сдвигах
В c/c++ существуют операторы сдвига <<(сдвиг влево) и >>(сдвиг вправо). Однако сдвиг может быть арифметическим (с сохранением знака сдвигаемого числа) и логическим (без сохранения знака).
Как выполнить арифметический/логический сдвиг на c/c++?
1) Арифметический сдвиг
вправо влево
0xfffe>>1=0xffff (-2>>1=-1)
выполняется просто
unsigned short shift = 0x1;
short src = 0xfffe;
short out = src >> shift;

0xfffe<<1=0xfffc (-2<<1=-4)>

unsigned short shift = 0x1;
short src = 0xfffe;
short out = src >> shift;

сработает, но скажем для примера 0x8001<<1=0x8002 такой код будет неверен . Следовательно, необходимо сохранять знак

out=(out>0)?((src>>shift)&0x7fff):((src>>shift)|0x8000)

2) Логический сдвиг

вправо влево
0xfffe>>1=0x7fff
unsigned short shift = 0x1;
unsigned short src = 0xfffe;
short out = src >> shift;

0x7ff0<<0x1=0xffe0

unsigned short shift = 0x1;
unsigned short src = 0xfffe;
short out = src <<>

Итак, неочевидные моменты. Если делать сдвиг над беззнаковым типом, то он ведет себя, как логический и не надо ждать от программы, что она будет сохранять знак (умножать/делить на 2 в степени величины сдвига). Если же делать сдвиг над знаковыми типом, то не надо ждать от программы, что она просто подвинет биты в числе.

Что почитать

1) Википедия. Битовый сдвиг

2) МСДН Bitwise shift operator