Быстрое разделение на GCC/ARM
Насколько я знаю, большинство компиляторов будут быстро делить, умножая и затем смещая бит вправо. Например, если вы проверите этот поток SO, в нем говорится, что когда вы попросите компилятор Microsoft выполнить деление на 10, он умножит дивиденд на 0x1999999A (что составляет 2 ^ 32/10), а затем разделить результат на 2 ^ 32 (используя 32 смены вправо).
Пока все хорошо.
Как только я протестировал одно и то же деление на 10 на ARM, используя GCC, компилятор сделал что-то немного другое. Сначала он умножил дивиденд на 0x66666667 (2 ^ 34/10), затем разделил результат на 2 ^ 34. До сих пор это то же самое, что и Microsoft, за исключением использования более высокого множителя. После этого, однако, он вычитал (дивиденд/2 ^ 31) из результата.
Мой вопрос: почему в версии ARM есть дополнительное вычитание? Можете ли вы дать мне числовой пример, где без этого вычитания результат будет неправильным?
Если вы хотите проверить сгенерированный код, он ниже (с моими комментариями):
ldr r2, [r7, #4] @--this loads the dividend from memory into r2
movw r3, #:lower16:1717986919 @--moves the lower 16 bits of the constant
movt r3, #:upper16:1717986919 @--moves the upper 16 bits of the constant
smull r1, r3, r3, r2 @--multiply long, put lower 32 bits in r1, higher 32 in r3
asr r1, r3, #2 @--r3>>2, then store in r1 (effectively >>34, since r3 was higher 32 bits of multiplication)
asr r3, r2, #31 @--dividend>>31, then store in r3
rsb r3, r3, r1 @--r1 - r3, store in r3
str r3, [r7, #0] @--this stores the result in memory (from r3)
Ответы
Ответ 1
После этого, однако, он вычитал (дивиденд/2 ^ 31) из результата.
Фактически, он вычитает dividend >> 31, который -1 для отрицательного dividend и 0 для неотрицательного дивиденда, когда правые сдвиговые отрицательные целые числа являются арифметическими сдвигами вправо (и int имеет ширину 32 бит).
0x6666667 = (2^34 + 6)/10
Итак, для x < 0 имеем, записывая x = 10*k + r с -10 < r <= 0,
0x66666667 * (10*k+r) = (2^34+6)*k + (2^34 + 6)*r/10 = 2^34*k + 6*k + (2^34+6)*r/10
Теперь арифметический сдвиг вправо отрицательных целых чисел дает слово v / 2^n, поэтому
(0x66666667 * x) >> 34
приводит к
k + floor((6*k + (2^34+6)*r/10) / 2^34)
Итак, нам нужно видеть, что
-2^34 < 6*k + (2^34+6)*r/10 < 0
Правильное неравенство легко, и k, и r неположительны, а не оба равны 0.
Для левого неравенства требуется немного больше анализа.
r >= -9
поэтому абсолютное значение (2^34+6)*r/10 не превосходит 2^34+6 - (2^34+6)/10.
|k| <= 2^31/10,
so |6*k| <= 3*2^31/5.
И остается проверить, что
6 + 3*2^31/5 < (2^34+6)/10
1288490194 < 1717986919
Yup, true.
Ответ 2
x SAR 31 0xffffffff (-1) для отрицательных значений x и 0x00000000 для положительных значений.
Итак, rsb вычитает -1 из результата (что совпадает с добавлением 1), если дивиденд был отрицательным.
Скажем, ваш дивиденд -60. С умножением и сдвигом вы получите результат -7, поэтому он вычитает -1 для получения ожидаемого результата -6.
