Модификация и деление по степени двойки для любого числа со знаком
Я знаю формулу положительных чисел. например, учитывая целое положительное число X и любую степень двойки Y = 2^K, мы имеем
X / Y == X >> K
X % K == X & (Y - 1)
но что, если X отрицательно? Я не смог найти это в Интернете, но мне нужно это знать. Я хочу выполнить целочисленное деление/модификацию с помощью SSE, а делители - это степень двойки. (хотя это может быть не известно во время компиляции)
примечание: для модуля я ищу фактическое поведение С++, например -1 % 3 == -1 и -5 % 3 == -2
Глядя на clang x86-64, эта функция
int divide(int x) {
return x / 8;
}
компилируется в
lea eax, [rdi + 7]
test edi, edi
cmovns eax, edi // move edi to eax if edi is positive?
sar eax, 3 // i can only understand this part!
ret
и для модуля x % 8,
mov eax, edi
lea ecx, [rax + 7]
test edi, edi
cmovns ecx, edi
and ecx, -8
sub eax, ecx
ret
может кто-нибудь объяснить формулу или просто дать ссылку на то, откуда это взялось? Заранее спасибо.
@JoopEggen Я тоже об этом думал, но для этого требуется ветка, и когда я смотрю на компиляторы, такие как gcc или clang, они делают что-то более умное и не имеют ветки. (хотя есть один cmov)
SAR «округляется в сторону отрицательной бесконечности», поэтому для x в [-7,-1] SAR x, 3 будет давать -1 вместо 0. Добавление 7 в случае отрицательного числа приводит к тому, что это округление дает желаемый результат.
Ответы 1
Знаковый модуль/деление С++ (на мой взгляд) определен плохо. Вы получите гораздо более естественную структуру, если модуль всегда положителен, а деление всегда округляется до отрицательной бесконечности. Думаю, можно винить производителей процессоров за выбор подписанных инструкций деления.
Одним из случаев, когда это проявляется, является арифметический сдвиг со знаком. Естественно, это всегда округляется до отрицательной бесконечности. Итак, чтобы эмулировать деление C++, которое всегда округляется до нуля, вам нужно разделить оператор деления на два случая:
- Если положительный, мы переключаемся как обычно.
- Если отрицательный результат, мы вычисляем
floor((x + d - 1) / d)для эмуляцииceil(x / d), округляя его до нуля.
Итак, это объясняет следующее:
lea eax, [rdi + 7] // t = x + 7
test edi, edi // if x < 0
cmovns eax, edi // x = t
sar eax, 3 // ret = floor(x / 8)
ret
Теперь, при вычислении по модулю, мы имеем точно такой же сценарий. В дополнении до двух взятие младших k бит при выполнении по модулю 2^k уже дает всегда положительный модуль. Однако в C++ (из-за неудачного выбора округления деления до нуля) есть странный модуль, знак которого всегда совпадает с числителем.
Чтобы смоделировать это, мы вместо этого вычисляем остаток как x - round_to_zero(x / d) * d. Итак, вот что делает сборка:
mov eax, edi // orig = x
lea ecx, [rax + 7] // Same as before, see above.
test edi, edi
cmovns ecx, edi
// sar ecx, 3 // As an optimization we
// shl ecx, 3 // replace (x >> 3) << 3
and ecx, -8 // with x & ~((1 << 3) - 1).
sub eax, ecx // ret = orig - round_to_zero(x / 8)
ret
Большое спасибо! теперь это имеет большой смысл <3
Итак, очевидно, что для отрицательного x, положительного y:
x % y == -(-x % y)иx / y == -(-x / y).