Как я могу использовать сдвиг бит для замены целочисленного деления?

Question

Я понимаю, как сделать это для степеней 2, так что это не мой вопрос.

Например, если я хочу найти 5% числа, используя сдвиг бит вместо целочисленного деления, как бы я рассчитал это?

Так что вместо (x * 20/19) я мог бы сделать (x * 100 >> 11). Теперь это не правильно, но это близко, и я пришел к этому методом проб и ошибок. Как бы я определил наиболее возможный точный сдвиг для использования?

Answer 1

Лучший подход - позволить компилятору сделать это за вас.Вы просто пишете

a/b

на выбранном вами языке, и компилятор генерирует биты.

РЕДАКТИРОВАТЬ (надеюсь, вы не против, яm добавление подкрепления к вашему ответу:

#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

да, вот оно, 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)
• Load (movl 0x ...) и умножьте на (imull) дробь с фиксированной точкой, получив 64-битный результат (это 32-битный код)
• Разделите старшие 32 бита результата на 8 (sarl), обратите внимание, как это обрабатываетсяотрицательные числа
• Разделите младшие 32 бита результата на INT_MAX (sarl), чтобы получить либо 0, либо -1
• Правильно округлить старший результат, добавив 1 (вычитая -1), еслиnecessари.

Answer 2

Это не имеет смысла, потому что то, что вы пытаетесь сделать, не оптимизирует полученный процесс !!!

Эй, я нигде не прочитал в вашем вопросе, что вы намеревались оптимизировать.

Electric Engg люди никогда не перестают быть любопытными независимо от «полезности».Мы как навязчивые навязчивые накопители предметов, о которых вы читаете в новостях, где они складывают свои чердаки, подвалы, спальни и гостиные с мусором, который, по их мнению, пригодится однажды.По крайней мере, так было, когда я учился в школе Энгга чуть менее 30 лет назад.Я призываю вас продолжать поиски «бесполезных» знаний, которые, по-видимому, имеют мало возможностей для оптимизации вашей жизни или образа жизни.Зачем зависеть от компилятора, если вы можете сделать это с помощью алгоритма, написанного вручную ?!Ях?Знаешь, будь немного авантюристом. Хорошо, если вы отрицаете людей, которые выражают презрение к вашему стремлению к знаниям.

Вспомните, как вас учили в средней школе, как вас учили делить?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.

Выше, как вы уже знаете, есть ИСТИННОЕ подразделение.Что достигается путем вычитания сдвинутым делителем.

То, что вы хотите, - это добиться того же, просто сместив дивиденд.К сожалению, этого нельзя сделать, если делитель не имеет экспоненциальной степени 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.

Вуаля.

Как вы определяете 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.

Я надеюсь, что мои бинарные манипуляции выше не будут иметь ошибок или опечаток.Если это так, тысячи извинений.

Answer 3

Если вас интересует математика, стоящая за ней, прочитайте Восторг Хакера Генри Уоррена.

Если вас интересует оптимизированный код, просто напишите, что легче всего читать людям. Например:

int five_percent(int x) {
  return x / 20;
}

Когда вы компилируете эту функцию, используя g++ -O2, она не будет выполнять фактическое деление, а вместо этого будет использовать магическое умножение, сдвиг битов и коррекцию.

Answer 4

Предположим, у вас есть выражение a = b / c. Как упоминал гроптатыр, умножение происходит довольно быстро (и намного быстрее деления). Таким образом, основная идея состоит в том, чтобы преобразовать деление в умножение как: a = b * (1/c).

Теперь нам все еще нужно деление для вычисления значения 1/c, так что это будет работать, только если c известно априори. В то время как для вычисления с плавающей запятой этого достаточно, для целых чисел мы должны использовать другой прием: мы можем использовать для обратной величины значение 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;
}

РЕДАКТИРОВАТЬ: хорошая часть этого метода в том, что вы можете выбрать любой метод округления для деления, выбрав поправку (в данном случае это было 20 - 1 для округления до нуля).

Answer 5

Вы не можете делать все со сменами, вместо этого вам нужно будет использовать «магические» делители (см. Восторг хакеров).Магическое деление работает путем умножения числа на другое подходящее большое число, переворачивая его таким образом, чтобы получить ответ деления (mul / imul быстрее, чем div / idiv).Там магические константы являются уникальными только для каждого простого числа, кратные значения требуют сдвига, например: беззнаковое деление на 3 может быть представлено (на 32-битной) как x * 0xAAAAAAAB, деление на 6 будет (x * 0xAAAAAAAB) >> 1, деление на 12 сместится на 2,24 на 3 и т. Д. (Это геометрический ряд 3 * (2 ^ x), где 0 <= x <32) </p>

Answer 6

Предположим, вы хотите приблизительно 5% от x, умножив на y и сдвинув на n. Поскольку 5% - это 1/20, а a >> n = a / 2 ⁿ , вы хотите решить

x / 20 ≈ x * y / 2 ⁿ (символ «≈» означает «примерно равный»)

, что упрощается до

y ≈ 2 ⁿ / 20

Так что, если n = 11, то

y ≈ 2 ⁿ / 20 = 2048/20 = 102 + 8/20

Таким образом, мы можем установить y = 102, что на самом деле лучше, чем 100, найденное методом проб и ошибок.

Как правило, мы можем поиграть с n, чтобы увидеть, можем ли мы получить лучший ответ.

Я работал над дробью 1/20, но вы должны быть в состоянии вычислить это для любой дроби p / q, следуя тому же методу.

Answer 7

Ну вообще:

• Получите простое разложение числа, вы разложите N на 2 ^ k * rest, затем вы можете использовать сдвиг битов на две степени. Пример: 20 = 2 ^ 2 * 5, поэтому для умножения на двадцать нужно умножить на 5, а затем использовать битовое смещение << 2
• Чтобы использовать сдвиг битов на не двух степенях, соблюдайте следующее для нечетного l: a * l = a * (l - 1) + a, теперь l - 1 является четным и, следовательно, разлагается на две степени, для которых применяется «трюк» сдвига битов.

Отделение может быть построено аналогично.