Как использовать смещение битов для замены целочисленного деления?
Я понимаю, как это сделать для полномочий 2, чтобы не мой вопрос.
Например, если я хочу найти 5% числа, используя сдвиг бит вместо целочисленного деления, как бы я вычислил это?
Итак, вместо (x * 20/19) я мог бы сделать (x * 100 → 11). Теперь это неправильно, но оно близко, и я пришел к нему с помощью проб и ошибок. Как определить наиболее возможный точный сдвиг для использования?
Ответы
Ответ 1
Лучший подход - позволить компилятору сделать это за вас. Вы просто пишете
a/b
на выбранном вами языке, а компилятор генерирует бит.
EDIT (надеюсь, вы не против, я добавляю подкрепление вашему ответу:
#include <stdio.h>
int main(int argc, char **argv) {
printf("%d\n", argc/4);
}
Очевидно, что самая быстрая вещь - argc>>2. Давайте посмотрим, что произойдет:
.file "so3.c"
.section .rodata
.LC0:
.string "%d\n"
.text
.globl main
.type main, @function
main:
pushl %ebp
movl %esp, %ebp
andl $-16, %esp
subl $16, %esp
movl 8(%ebp), %eax
movl %eax, %edx
sarl $31, %edx
shrl $30, %edx
leal (%edx,%eax), %eax
sarl $2, %eax
movl %eax, %edx
movl $.LC0, %eax
movl %edx, 4(%esp)
movl %eax, (%esp)
call printf
leave
ret
.size main, .-main
.ident "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3"
.section .note.GNU-stack,"",@progbits
yup, вот оно, sarl $2, %eax
ИЗМЕНИТЬ 2 (Извините, что куча включена, но 20/19 немного сложнее...)
Я только что заменил argc*20/19 на argc/4, и это математика, которая выходит:
0000000100000f07 shll $0x02,%edi
0000000100000f0a movl $0x6bca1af3,%edx
0000000100000f0f movl %edi,%eax
0000000100000f11 imull %edx
0000000100000f13 sarl $0x03,%edx
0000000100000f16 sarl $0x1f,%edi
0000000100000f19 subl %edi,%edx
Итак, процесс
- Умножить ввод на 4 (shll)
- Загрузить (movl 0x...) и умножить на (imull) долю с фиксированной точкой, получив 64-битный результат (это 32-разрядный код)
- Разделите 32-разрядный результат высокого порядка на 8 (sarl), обратите внимание, как это обрабатывает отрицательные числа
- Разделите 32 бита результата младшего порядка на INT_MAX (sarl), чтобы получить либо 0, либо -1
- Правильно округлите результат высокого порядка, добавив 1 (вычитая -1), если это необходимо.
Ответ 2
Это не имеет никакого смысла, потому что то, что вы пытаетесь сделать, не оптимизирует результирующий процесс.
Эй, я не читал нигде в вашем вопросе, что у вас есть намерение оптимизировать.
Электрические люди Engg никогда не перестают быть любопытными, независимо от "полезности". Мы похожи на навязчивых навязчивых хранителей предметов, о которых вы читаете в новостях, где они складывают свои чердаки, подвалы, спальни и жилые комнаты с барахлом, который, по их мнению, когда-нибудь пригодится. По крайней мере, это было так, когда я учился в школе Энгг чуть меньше 30 лет назад. Я призываю вас продолжить поиски, чтобы накопить "бесполезные" знания, которые, как представляется, мало возможностей для оптимизации вашей жизни или образа жизни. Зачем зависеть от компилятора, когда вы можете сделать это с помощью ручного алгоритма?! Ях? Знаешь, будьте немного предприимчивы. Ok enuf раскрыть людей, которые выражают презрение к вашему стремлению к знаниям.
Вспомните в своей средней школе, как вас учили делать свое разделение? 437/24, например
_____
24|437
018
-----
24|437
24
-----
197
24
-----
5
Число, подлежащее делению, 437, называется дивидендом. 24 - делитель, результатом 18 является фактор, а 5 - остаток. Например, когда вы подаете свои налоги, вам нужно заполнить прибыль, полученную вами от акций "дивиденды", что является неправильным. То, что вы заполняете в налоговой форме, кратно частному от одного огромного куска дивидендов. Вы не получили дивиденды, а части дивидендов - иначе это означало бы, что вам принадлежит 100% акций.
___________
11000|110110101
000010010
-----------
11000|110110101
11000
----------
000110101 remainder=subtract divisor from dividend
11000000 shift divisor right and append 0 to quotient until
1100000 divisor is not greater than remainder.
110000 Yihaa!
----------
000101 remainder=subtract shifted divisor from remainder
11000 shift divisor right and append 0 to quotient until
1100 divisor is not greater than remainder.
----------
oops, cannot shift anymore.
Выше, как вы уже знаете, это TRUE-деление. Это достигается вычитанием сдвинутым делителем.
То, что вы хотите, - это добиться того же, просто переместив дивиденд. Это, к сожалению, невозможно сделать, если дивизор не является показательной степенью 2 (2,4,8,16). Это очевидный факт двоичной арифметики. Или, по крайней мере, я не знаю ни одного метода, который мог бы сделать это без аппроксимации и интраполяционных методов.
Следовательно, вы должны использовать комбинацию смещения дивидендов и истинного деления.
например.
24 = 2 x 2 x 2 x 3
Сначала разделите 437 на 8, используя двоичный сдвиг, чтобы получить 010010, а затем используйте истинное деление для деления на 3:
010010
--------
11|110110
11
-------
011
11
-----
0
который работает до 010010 = 18.
Voila.
Как вы определяете 24 = 2 ^ 8 x 3?
Переместив 11000 вправо, пока не нажмете 1.
Это означает, что вы можете сдвинуть дивиденд столько же раз, сколько и сдвиг дивизора, пока дивизор не достигнет 1.
Поэтому, очевидно, этот метод не сработает, если делитель нечетен.
например, он не будет работать для делителя 25, но он будет немного работать для делителя 50.
Может быть, существуют прогностические методы, которые могли бы интерполировать такой делитель, как 13, между 2 ^ 3 = 8 и 2 ^ 4 = 16. Если есть, я не знаком с ними.
Что вам нужно исследовать - это использовать ряд чисел. Например, деление на 25:
1 1 1 1 1
__ = __ - ___ - ___ + ___ - ... until the precision you require.
25 16 64 128 256
где общий вид ряда
1 1 b1 bn
_ = ___ + _______ + ... + ______
D 2^k 2^(k+1) 2^(k+n)
где bn равно либо -1, 0 или +1.
Я надеюсь, что моя бинарная манипуляция выше не будет иметь ошибок или опечаток. Если да, то тысячи извинений.
Ответ 3
Предположим, что у вас есть выражение a = b / c. Как упоминал Хроптатыр, умножение происходит довольно быстро (и оно намного быстрее, чем деление). Итак, основная идея состоит в том, чтобы преобразовать деление в умножение как: a = b * (1/c).
Теперь нам все еще нужно деление для вычисления рецептурного 1/c, поэтому это будет работать только в том случае, если c известен априори. Хотя для вычисления с плавающей запятой достаточно, для intereges нам нужно использовать другой трюк: мы можем использовать для обратного значения c значение some_big_number / c, так что, наконец, мы вычислим a2 = b * (some_big_number / c), что равно some_big_number * b/c. Поскольку нас интересует значение b/c, мы должны разделить окончательный результат на some_big_number. Если его выбрали равной 2, то окончательное деление будет быстрым.
Пример:
// we'll compute 1/20 of the input
unsigned divide_by_20(unsigned n){
unsigned reciprocal = (0x10000 + 20 - 1) / 20; //computed at compile time, but you can precompute it manually, just to be sure
return (n * reciprocal) >> 16;
}
EDIT: хорошая часть этого метода заключается в том, что вы можете выбрать любой метод округления для деления, выбирая коррекцию (в данном случае это было 20 - 1 для округления к нулю).
Ответ 4
Если вы заинтересованы в математике за ней, прочитайте "Хакерский восторг" Генри С. Уоррена.
Если вы заинтересованы в оптимизированном коде, просто напишите, что проще всего прочитать людям. Например:
int five_percent(int x) {
return x / 20;
}
Когда вы скомпилируете эту функцию с помощью g++ -O2, она не будет выполнять фактическое деление, но вместо этого произойдет небольшое умножение, бит-сдвиг и коррекция.
Ответ 5
Вы не можете делать все со сменой, вместо этого вам придется использовать "волшебные" дивизоры (см. хакеры). Магическое подразделение работает, умножая число на другое достаточно большое число, перевернув его таким образом, чтобы дать ответ на деление (mul/imul быстрее, чем div/idiv). Там магические константы уникальны только для каждого штриха, кратные требуют сдвига, например: беззнаковое деление на 3 может быть представлено (на 32 бит) как x * 0xAAAAAAAB, деление на 6 будет (x * 0xAAAAAAAB) >> 1 деление на 12 будет смещаться на 2, 24 на 3 и т.д. (Его геометрический ряд 3 * (2 ^ x), где 0 <= x < 32)
Ответ 6
Предположим, вы хотите приблизительно 5% от x умножить на y и сдвинуть на n. Так как 5% равно 1/20, а → n = a/2 n вы хотите решить
x/20 ≈ x * y/2 n (символ "≈" означает "приблизительно равный" )
что упрощается до
y ≈ 2 n/20
Итак, если n = 11, то
y ≈ 2 n/20 = 2048/20 = 102 + 8/20
Таким образом, мы можем установить y = 102, что на самом деле лучше, чем 100, найденные методом проб и ошибок.
Как правило, мы можем играть с n, чтобы узнать, можем ли мы получить лучший ответ.
Я проработал это для фракции 1/20, но вы должны уметь это сделать для любой доли p/q, следуя тому же методу.
Ответ 7
Хорошо в целом:
- получить основное факторизацию числа, вы разложите N на 2 ^ k * rest, тогда вы можете использовать смещение битов по двум параметрам. Пример: 20 = 2 ^ 2 * 5, поэтому умножить на двадцать умножить на 5, а затем использовать сдвиг бит
<< 2
- Чтобы использовать смещение битов на не-двух степенях, наблюдайте следующее для нечетного
l: a * l = a * (l - 1) + a, теперь l - 1 четное и, следовательно, разлагается на две мощности, для которых применяется "трюк" смещения бит.
Подразделение может быть построено аналогично.
