1. Операции сдвига
Сначала вкратце самые основы. Как известно, в Java все примитивные типы знаковые, и есть несколько вариантов побитовых операций сдвига:- >> сдвиг вправо
- << сдвиг влево
- >>> сдвиг вправо («беззнаковый»)
Резюме: в 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)Теперь всё должно стать понятным, не допускайте таких простых ошибок.
спасибо, полезно)
ОтветитьУдалитьпожалуйста) статья, правда, древняя — перенёс как было. сейчас бы ещё дописал что-нибудь интересное, но лень)
УдалитьНе могу понять где это можно использовать.
ОтветитьУдалитьЭ... что именно использовать?
УдалитьСпасибо за статью. Очень помогла. А то я сегодня голову ломал - что ж со сдвигом в byte не так))
ОтветитьУдалить