March 22nd, 2011

Сокращение правого операнда побитового сдвига

Операторы побитового сдвига берут левый операнд и сдвигают его двоичное представление на количество бит (вправо >> или влево <<), указанных в правом операнде. В простейших случаях такие операции эквивалентны делению или умножению на степень двойки. Некоторые особенности появляются, если берутся числа отрицательные или знаковые. Например, в C++ (Глава Стандарта 5.8) сдвиг влево отрицательного значения ведет к undefined behavior, а сдвиг право определяется реализацией. Однако сдвиг положительного (или беззнакового) значения вправо E1 >> E2 всегда должен быть эквивалентен целой части E1 / 2E2.

Кстати, есть язык, в котором нет беззнаковых типов. В нем сдвиг вправо старшие биты заполняет не нулем, а значением знакового бита (для отрицательных чисел единицей). Поскольку это не всегда ожидаемое поведение, в языке есть специальный оператор беззнакового сдвига вправо >>>. Старшие биты он заполняет нулем.

Но это еще не все. В спецификациях языков C# (п. 14.8) и Java (п. 15.19) есть такое понятие, как сокращение правого операнда. В действительности сдвиг осуществляется не на то число бит, которое записано в правом операнде, а на его значение по модулю разрядности левого операнда. То есть происходит примерно следующее:
E1 >> (E2 % (sizeof(E1) * 8)) или, точнее,
E1 >> (E2 & (sizeof(E1) * 8 – 1))
Это приводит к неожиданным спецэффектам, например, сдвиг на 1000000 вообще не будет делать никаких сдвигов. Трогательную историю, зачем так было сделано, можно почитать здесь.

А вот совершенно внезапным для меня оказалось, что некоторые популярные компиляторы C++ тоже делают сокращение, хотя никакого намека на это я не нашел ни в Стандарте, ни в аннотированном руководстве. Я проверил в Visual C++ 2005, MinGW 4.5.2 и CodeGear C++ 2009 – во всех присутствует сокращение для всех целочисленных типов (кроме, разве что, long long, для которого оно есть лишь в MinGW).

Если кто-то знает причину этого странного явления, расскажите, а?

UPD: Visual C++ 2008/2010 и Intel C++ Compiler 11 выдают аналогичный результат.
Посмотрел, во что оно компилируется (VC++), получается что-то вроде:
mov esi, dword ptr [E1]
mov eсx, dword ptr [E2]
sar esi, cl
Здесь следует обратить внимание на семантику мнемоники sar. В качестве второго операнда может быть только конкретное значение, либо регистр cl (младший байт регистра ecx). В последнем случае происходит сокращение cl по маске 0x1F, то есть по модулю 32.

На код вида 121 >> 1000000; VC++ выдает предупреждение "shift count negative or too big, undefined behavior". Причины, почему too big приводят к ub, находятся за горизонтом моего непонимания, однако уже объясняют, почему все компиляторы ведут себя undefined.
  • Current Music
    Draconian — [Arcane Rain Fell #08] Death, Come Near Me