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

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

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

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

 mikerobi03 окт. 2010 г., 19:02
Что заставляет вас думать, что это возможно?
 Jonathan Grynspan03 окт. 2010 г., 18:58
Зачем? Это должно быть оптимизацией? Что вы оптимизируете? Вы уверены, что это нужно оптимизировать?
 Potatoswatter04 окт. 2010 г., 00:25
Также все - этоявляется иногда действительная оптимизация. Если вам нужно умножить большое количество значений на одинаковую, но переменную дробь, то преобразование деления в сложное умножение может повысить производительность.
 Amadan03 окт. 2010 г., 19:03
@ Джонатан: +1; что бы это ни было, это не оптимизация ... :)
 brainjam03 окт. 2010 г., 19:07
Вы имеете в виду х / 20 вместо (х * 20/19)? Поскольку первый составляет 5%, второй более 100%.
 Potatoswatter04 окт. 2010 г., 00:23
@Бен:0.0488... близко к1/19не20/19, Во всяком случае, я тоже неправильно понял, я имел в видуx + (x *...)
 Ben Voigt04 окт. 2010 г., 00:21
@Potatoswatter: нет,x * 100 >> 11 являетсяx * 100 / 2048 являетсяx * .048828125 что является разумным приближением к 5%.x * 102 >> 11 лучше, как указал брейнджем, ноx * 51 >> 10 столь же хорош и менее склонен к переполнению, в то время какx * 205 >> 12 имеет значительно меньшую ошибку.
 Ben Voigt04 окт. 2010 г., 00:28
@Potatoswatter: в строке выше написано "найди 5% от числа". Поскольку это соответствует примеру, я могу только предположить, что «20/19», на которых вы сосредоточились, является ошибкой.
 phimuemue03 окт. 2010 г., 19:02
Джонатан прав: если вы хотите использовать это как оптимизацию, вам лучше позволить компилятору сделать всю работу за вас, так как компиляторы лучше, чем (большинство) люди, делают такие вещи. Однако, если вы просто хотите это знать, я не думаю, что есть краткое руководство по переводу между делением и сдвигом.
 Potatoswatter04 окт. 2010 г., 00:33
@Ben: Возможно. Я думаю, что он действительно хочет, чтобыдобавлять 5%. Похоже, мы согласны, что 19 в знаменателе, вероятно, ошибка.
 Potatoswatter03 окт. 2010 г., 19:27
Я думаю он имеет ввидуx - (x * 100 >> 11).

Ответы на вопрос(7)

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 для округления до нуля).

 ergosys03 окт. 2010 г., 22:29
Для значений со знаком делим на 65536 вместо сдвига на 16, компилятор преобразуется в сдвиг и исправление.

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

Восторг Хакера Генри С. Уоррен.

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

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

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

шешь

a/b

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

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

#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)Загрузите (movl 0x ...) и умножьте на (imull) дробь с фиксированной точкой, получив 64-битный результат (это 32-битный код)Разделите старшие 32 бита результата на 8 (sarl), обратите внимание, как это обрабатывает отрицательные числаРазделите младшие 32 бита результата на INT_MAX (sarl), чтобы получить либо 0, либо -1Правильно округлите результат высокого порядка, добавив 1 (вычитая -1), если необходимо.
 Larry K04 окт. 2010 г., 00:19
+1 Любите ассемблерный код!
 Potatoswatter03 окт. 2010 г., 19:25
+1 - отработка битов вручную - рутина, и лучший способ изучить процесс - посмотреть на скомпилированный вывод.
 High Performance Mark04 окт. 2010 г., 10:07
@Potatoswatter: Я упал baaaddd, зарабатывая столько репутации от ваших усилий. Не очень плохо, это не заставит меня спать по ночам, но немного плохо :-)
 SingleNegationElimination03 окт. 2010 г., 21:43
Я добавил вывод компилятора, чтобы продемонстрировать, насколько вы правы!
 Potatoswatter04 окт. 2010 г., 17:20
@Mark: Мех, если бы мне пришлось описать это в общих чертах, это было бы более полезно. Нет смысла позволять представителю на самом деле что-либо решать.

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

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

 hroptatyr03 окт. 2010 г., 19:27
Кто это сказал? ОП хочет знать, как превратить целочисленное умножение в сдвиг битов, я только что описал общую процедуру.
 hroptatyr03 окт. 2010 г., 19:59
Да и кстати, никогда не суди, пока вы не измерили, я только что обнаружил, чтоimul будет 3 цикла на моем процессоре, тогда как мое решение сshl иadd занимает 2 цикла.
 Potatoswatter03 окт. 2010 г., 21:36
В любом случае, вопрос не столько в замене умножения, сколько в делении, которое вы вообще не решаете. Для этого требуется получить результат умножения высокого порядка, который нельзя представить с помощью операторов C. (По крайней мере, не получить полную ширину целочисленного регистра.) Это математический прием с фиксированной запятой.
 Potatoswatter03 окт. 2010 г., 19:24
Это бессмысленно. Умножение на 5 включает любую стоимость сдвига<< 2, Задача состоит в том, чтобы умножить на любое рациональное число всего одну или две инструкции без деления, не разложить число и использовать неопределенное количество insns.
 Potatoswatter03 окт. 2010 г., 21:33
shl иadd умножает только на 5. Вам все еще нужен другой insn, чтобы снова сдвинуться. Компилятор должен быть достаточно умен, чтобы понять это и не производитьimul если он действительно хуже, хотя для переносимости он может быть не специализирован для вашего чипа, а более высокий счетчик команд может вызвать другие перегрузки.

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

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

что упрощает

у ≈ 2n/ 20

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

у ≈ 2n/ 20 = 2048/20 = 102 + 8/20

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

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

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

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

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

Люди-электрики никогда не перестают быть любопытными независимо от «полезности». Мы как навязчивые навязчивые накопители предметов, о которых вы читаете в новостях, где они складывают свои чердаки, подвалы, спальни и гостиные с мусором, который, по их мнению, пригодится однажды. По крайней мере, так было, когда я учился в школе Энгга чуть менее 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.

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

Ваш ответ на вопрос