21 марта 2012 г.

Битовые сдвиги и приведения в Java: подводные камни

1. Операции сдвига

Сначала вкратце самые основы. Как известно, в Java все примитивные типы знаковые, и есть несколько вариантов побитовых операций сдвига:
  • >> сдвиг вправо
  • << сдвиг влево
  • >>> сдвиг вправо («беззнаковый»)
Как видно, в дополнение к классическим сдвигам есть также «беззнаковый» сдвиг, который игнорирует знаковый левый бит и сдвигает его как обычный. Также эти сдвиги называются, соответственно, логический (когда первый бит теряется а последний заполняется нулём) и арифметический (аналогично, но значение считается значением в дополнительном коде и последний бит (знаковый) сохраняет своё значение).Например, в C++, сдвиги есть только «правые» и «левые», при этом (если не ошибаюсь) для отрицательных чисел «поведение определяется реализацией». Также в машинных кодах/ассемблерах (в интеле, например) есть операции циклического сдвига (которые переносят бит вместо сдвигаемого, как вариант через бит переноса).
Резюме: в Java циклического сдвига нет, обычные сдвиги являются арифметическими, также имеется правый логический сдвиг (левый логический сдвиг, очевидно, синонимичен левому арифметическому), как следствие поведение каждого строго определено (в отличие от всяких C++).
Итак, при сдвиге отрицательных чисел имеется разница в использовании операторов >> и >>>.
Простыми словами: первая операция распространяет знаковый (левый) бит направо до конца, вторая заполняет нулями. У положительных чисел, стало быть, результат будет одинаков.
Пример:
int i = 192;
i       00000000 00000000 00000000 11000000 (192)
i<<1    00000000 00000000 00000001 10000000 (384)
i>>1    00000000 00000000 00000000 01100000 (96)
i>>>1   00000000 00000000 00000000 01100000 (96)
int i = -192;
i       11111111 11111111 11111111 01000000 (-192/4294967104)
i<<1    11111111 11111111 11111110 10000000 (-384/4294966912)
i>>1    11111111 11111111 11111111 10100000 (-96/4294967200)
i>>>1   01111111 11111111 11111111 10100000 (2147483552)
Итак, можно сказать, что операция >>> — это «настоящий» «битовый» сдвиг, а >> это эквивалент деления на 2 как для положительных, так и для отрицательных чисел. Такое вот поведение по умолчанию.

Интересное замечание: есть некоторое отличие от целочисленного деления на 2: если сдвигать отрицательное число вправо, то сначала это аналогично целочисленному делению на 2, но когда от числа останется -1, то при следующих сдвигах остаётся всё время -1.
При целочисленном делении же получится, как понятно, 0. То есть происходит округление не к нулю, как при целочисленном делении, а к -1.

2. reduction правого операнда операции сдвига

Здесь тоже таится некоторая неожиданность. Это свойственно не только JVM, но и большинству обычных процессоров. Нельзя сдвинуть на количество бит, большее, чем разрядность операнда. При этом происходит неявное сокращение правого (кол-во бит) операнда.
Пример:

i       00000000000000000000000000000001 (1)
...
i<<29   00100000000000000000000000000000 (536870912)
i<<30   01000000000000000000000000000000 (1073741824)
i<<31   10000000000000000000000000000000 (-2147483648/2147483648)
i<<32   00000000000000000000000000000001 (1)
Здесь мы вроде как можем ожидать, что единичка пропадёт и останутся все нули, но это не так. Пример второй:
i       11111111111111111111111111111111 (-1/4294967295)
i>>>1   01111111111111111111111111111111 (2147483647)
...
i>>>30  00000000000000000000000000000011 (3)
i>>>31  00000000000000000000000000000001 (1)
i>>>32  11111111111111111111111111111111 (-1/4294967295)
Здесь аналогично - неподготовленному кодеру думается, что единица пропадёт и останется ноль, но мы знаем, что это не так. Ещё пример:
i       11111111111111111111111101000000 (-192/4294967104)
i>>1    11111111111111111111111110100000 (-96/4294967200)
...
i>>30   11111111111111111111111111111111 (-1/4294967295)
i>>31   11111111111111111111111111111111 (-1/4294967295)
i>>32   11111111111111111111111101000000 (-192/4294967104)
С какой-то стороны ещё интереснее, всё время делится сколько бы мы не сдвигали, но при reduction снова всё сначала начинается. Т.е. заметку из п.1 про округление к -1 при делении на /2 надо с учётом этого воспринимать.

3. arithmetic promotion операторов

Здесь вообще может получиться засада, если не понимать подобных основ. Как оказалось, многие как раз не понимают. Итак, арифметическое распространение в Java проводится перед операциями и гарантирует расширение каждого операнда по крайней мере до int. Если же один и операндов long, то до long. В итоге, если сдвигаемая переменная по разрядности меньше, то будет не совсем правильно, а иногда совсем неправильно. При этом как раз часто оперируют с битами на типе byte, это порой удобно, например, всё при тех же реализациях всяких протоколов. Тут почти всегда происходит косяк. Например, байт 10000001 и при сдвиге вправо через >> и при сдвиге через >>> станет выглядеть так: 11000000. Большинство из тех, у кого я это спросил в этом месте попались. Кстати, вспомнил что отвечал на такое уже где-то: http://ru-java.livejournal.com/811051.html Внимание: при приведении типов при расширении разрядности расширяется знаково. При сжатии разрядности просто отбрасываются байты лишние. Демонстрация того, как выглядит преобразование в битах:
byte b = -127;
b       10000001 (-127/129)
(int)b  11111111 11111111 11111111 10000001 (-127/4294967169)

int i = -127;
i       11111111 11111111 11111111 10000001 (-127/4294967169)
(byte)i 10000001 (-127/129)

int i = 128;
i       00000000 00000000 00000000 10000000 (128)
(byte)i 10000000 (-128/128)

int i = 256;
i       00000000 00000000 00000001 00000000 (256)
(byte)i 00000000 (0)

int i = -256;
i       11111111 11111111 11111111 00000000 (-256/4294967040)
(byte)i 00000000 (0)
Стало быть, основная засада ожидает нас при логическом сдвиге >>> отрицательных значений, ибо остальные (арифметические) сдвиги ведут себя более-менее ожидаемо с точки зрения знаков. Для положительных значений всё так же логично. Теперь пример с байтом 10000001 должен стать понятным:
byte b = -127;
b               10000001 (-127/129)
b<<1            11111111 11111111 11111111 00000010 (-254/4294967042)
b>>1            11111111 11111111 11111111 11000000 (-64/4294967232)
b>>>1           01111111 11111111 11111111 11000000 (2147483584)
(byte)(b<<1)    00000010 (2)
(byte)(b>>1)    11000000 (-64/192)
(byte)(b>>>1)   11000000 (-64/192)
Также не забывайте о расширении до long. Например, при накладывании маски можно обломиться, если забыть поставить L для длинной маски:
long w = -1;
w               1111111111111111111111111111111111111111111111111111111111111111 (-1)
w & 0xFFFFFFFF  1111111111111111111111111111111111111111111111111111111111111111 (-1)
w & 0xFFFFFFFFL 0000000000000000000000000000000011111111111111111111111111111111 (4294967295)
Почему так происходит. Происходит расширение маски до long. При этом нам теперь понятно, что числа (long)0xFFFFFFFF и 0xFFFFFFFFL совершенно разные:
(long)0xFFFFFFFF    1111111111111111111111111111111111111111111111111111111111111111 (-1)
0xFFFFFFFFL         0000000000000000000000000000000011111111111111111111111111111111 (4294967295)
Теперь всё должно стать понятным, не допускайте таких простых ошибок.

5 комментариев:

  1. Ответы
    1. пожалуйста) статья, правда, древняя — перенёс как было. сейчас бы ещё дописал что-нибудь интересное, но лень)

      Удалить
  2. Не могу понять где это можно использовать.

    ОтветитьУдалить
  3. Спасибо за статью. Очень помогла. А то я сегодня голову ломал - что ж со сдвигом в byte не так))

    ОтветитьУдалить