Когда я компилирую этот код с VC ++ 10:
DWORD ran = rand();
return ran / 4096;
Я получаю эту разборку:
299: {
300: DWORD ran = rand();
00403940 call dword ptr [__imp__rand (4050C0h)]
301: return ran / 4096;
00403946 shr eax,0Ch
302: }
00403949 ret
который является чистым и лаконичным и заменяет деление на степень два логическим сдвигом вправо.
Тем не менее, когда я компилирую этот код:
int ran = rand();
return ran / 4096;
Я получаю эту разборку:
299: {
300: int ran = rand();
00403940 call dword ptr [__imp__rand (4050C0h)]
301: return ran / 4096;
00403946 cdq
00403947 and edx,0FFFh
0040394D add eax,edx
0040394F sar eax,0Ch
302: }
00403952 ret
который выполняет некоторые манипуляции перед выполнением правильного арифметического сдвига.
Зачем нужны эти дополнительные манипуляции? Почему арифметического сдвига недостаточно?
Причина в том, что беззнаковое деление на 2 ^ n может быть реализовано очень просто, тогда как знаковое деление несколько сложнее.
unsigned int u;
int v;
u / 4096
эквивалентно u >> 12
для всех возможных значений u
,
v / 4096
является НЕ эквивалентно v >> 12
— это ломается, когда v < 0
, поскольку направление округления отличается для сдвига и деления, когда задействованы отрицательные числа.
«дополнительные манипуляции» компенсируют тот факт, что арифметическое смещение вправо округляет результат до отрицательной бесконечности, тогда как деление округляет результат до нуля.
Например, -1 >> 1
является -1
, в то время как -1/2
является 0
,
Из стандарта С:
Когда целые числа делятся, результатом оператора / является
алгебраический фактор с любой дробной частью отбрасывается.105) Если
фактор a / b представим, выражение (a / b) * b + a% b должно
равно а; в противном случае поведение как a / b, так и% b не определено.
Нетрудно придумать примеры, когда отрицательные значения для a не следуют этому правилу с чисто арифметическим сдвигом. Например.
(-8191) / 4096 -> -1
(-8191) % 4096 -> -4095
который удовлетворяет уравнению, тогда как
(-8191) >> 12 -> -2 (assuming arithmetic shifting)
не деление с усечением, и, следовательно, -2 * 4096 - 4095
наверняка не равно -8191.
Обратите внимание, что смещение отрицательных чисел на самом деле определяется реализацией, поэтому выражение C (-8191) >> 12
не имеет в целом правильного результата в соответствии со стандартом.