Как я могу размножать и делить, используя только смещение и добавление битов?

Как я могу размножать и делить, используя только смещение и добавление битов?

    Чтобы умножить с точки зрения добавления и сдвига, вы хотите разложить одно из чисел по степеням двух, например:

    21 * 5 = 10101_2 * 101_2 (Initial step) = 10101_2 * (1 * 2^2 + 0 * 2^1 + 1 * 2^0) = 10101_2 * 2^2 + 10101_2 * 2^0 = 10101_2 << 2 + 10101_2 << 0 (Decomposed) = 10101_2 * 4 + 10101_2 * 1 = 10101_2 * 5 = 21 * 5 (Same as initial expression) 

    ( _2 означает основание 2)

    Как вы можете видеть, умножение можно разложить на добавление и перемещение и обратно. Это также объясняется тем, что умножение занимает больше времени, чем бит-сдвиги или добавление - это O (n ^ 2), а не O (n) в количестве бит. Реальные компьютерные системы (в отличие от теоретических компьютерных систем) имеют конечное число бит, поэтому умножение занимает постоянное кратное времени по сравнению с добавлением и сдвигом. Если я правильно помню, современные процессоры, если они правильно конвейерны, могут делать умножение примерно так же быстро, как и добавление, путаясь с использованием ALU (арифметических единиц) в процессоре.

    Ответ Эндрю Тулузы может быть расширен до разделения.

    Деление по целочисленным константам подробно рассматривается в книге «Хакерское наслаждение» Генри С. Уоррена (ISBN 9780201914658).

    Первая идея реализации деления – записать обратное значение знаменателя в базе два.

    Например, 1/3 = (base-2) 0.0101 0101 0101 0101 0101 0101 0101 0101 .....

    Итак, для 32-битной арифметики a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30) .

    Объединяя термины очевидным образом, мы можем уменьшить количество операций:

    b = (a >> 2) + (a >> 4)

    b += (b >> 4)

    b += (b >> 8)

    b += (b >> 16)

    Есть более интересные способы расчета деления и остатков.

    EDIT1:

    Если OP означает умножение и деление произвольных чисел, а не деление на постоянное число, то этот stream может быть полезен: https://stackoverflow.com/a/12699549/1182653

    EDIT2:

    Один из самых быстрых способов разделить на целые константы – использовать модульную арифметику и сокращение Montgomery: какой самый быстрый способ разделить целое на 3?

    X * 2 = 1 бит сдвиг влево
    X / 2 = 1 бит сдвига вправо
    X * 3 = сдвиг влево 1 бит, а затем добавьте X

    x << k == x multiplied by 2 to the power of k
    x >> k == x divided by 2 to the power of k

    Вы можете использовать эти сдвиги для выполнения любой операции умножения. Например:

    x * 14 == x * 16 - x * 2 == (x << 4) - (x << 1)
    x * 12 == x * 8 + x * 4 == (x << 3) + (x << 2)

    Чтобы разделить число на не-два, я не знаю ни одного простого способа, если вы не хотите реализовать некоторую низкоуровневую логику, использовать другие двоичные операции и использовать некоторую форму итерации.

    1. Левая смена на 1 позицию аналогична умножению на 2. Правый сдвиг аналогичен делению на 2.
    2. Вы можете добавить в цикл для умножения. Выбрав переменную цикла и добавочную переменную правильно, вы можете связать производительность. После того, как вы изучили это, вы должны использовать Муниципальное умножение

    Я перевел код Python на C. Приведенный пример имел небольшой недостаток. Если значение дивиденда, которое заняло все 32 бита, сдвиг не сработает. Я просто использовал 64-битные переменные внутри для решения этой проблемы:

     int No_divide(int nDivisor, int nDividend, int *nRemainder) { int nQuotient = 0; int nPos = -1; unsigned long long ullDivisor = nDivisor; unsigned long long ullDividend = nDividend; while (ullDivisor < ullDividend) { ullDivisor <<= 1; nPos ++; } ullDivisor >>= 1; while (nPos > -1) { if (ullDividend >= ullDivisor) { nQuotient += (1 << nPos); ullDividend -= ullDivisor; } ullDivisor >>= 1; nPos -= 1; } *nRemainder = (int) ullDividend; return nQuotient; } 

    Возьмите два числа, скажем 9 и 10, напишите их как двоичные – 1001 и 1010.

    Начните с результата, R, равным 0.

    Возьмите одно из чисел, 1010 в этом случае, мы назовем его A и сдвинем его на один бит, если вы отделите один, добавьте первое число, мы будем называть его B, R.

    Теперь сдвиг B остается на один бит и повторяется до тех пор, пока все биты не будут смещены из A.

    Легче понять, что происходит, если вы видите это, это пример:

      0 0000 0 10010 1 000000 0 1001000 1 ------ 1011010 

    Процедура деления целых чисел, которая использует сдвиги и добавления, может быть получена прямолинейно из десятичного деления на длинные руки, как учили в начальной школе. Выбор каждой цифры фактов упрощается, так как цифра равна 0 и 1: если текущий остаток больше или равен делителю, младший значащий бит частичного частного равен 1.

    Точно так же, как при декомпрессионном делении, цифры дивиденда считаются от наиболее значимых до наименее значимых, по одной цифре за раз. Это легко осуществить левым сдвигом в двоичном делении. Кроме того, частные биты собираются левым смещением текущих битов отношения на одну позицию, а затем добавлением нового бит частного.

    В classической компоновке эти две левые сдвиги объединяются в левое смещение одной пары регистров. Верхняя половина удерживает текущий остаток, нижняя половина начинается с дивиденда. Поскольку биты дивидендов переносятся в регистр остатка по левому сдвигу, неиспользуемые младшие значащие разряды нижней половины используются для накопления частных битов.

    Ниже приведен язык ассемблера x86 и реализация C этого алгоритма. Этот конкретный вариант деления shift & add иногда называют «невыполняющим» вариантом, поскольку вычитание делителя из текущего остатка не выполняется, если остаток больше или равен делителю. В C нет понятия флага переноса, используемого версией сборки в левом сдвиге пары регистров. Вместо этого он эмулируется, основываясь на наблюдении, что результат сложения по модулю 2 n может быть меньше, чем либо добавлять только в случае выполнения.

     #include  #include  #include  #define USE_ASM 0 #if USE_ASM uint32_t bitwise_division (uint32_t dividend, uint32_t divisor) { uint32_t quot; __asm { mov eax, [dividend];// quot = dividend mov ecx, [divisor]; // divisor mov edx, 32; // bits_left mov ebx, 0; // rem $div_loop: add eax, eax; // (rem:quot) << 1 adc ebx, ebx; // ... cmp ebx, ecx; // rem >= divisor ? jb $quot_bit_is_0; // if (rem < divisor) $quot_bit_is_1: // sub ebx, ecx; // rem = rem - divisor add eax, 1; // quot++ $quot_bit_is_0: dec edx; // bits_left-- jnz $div_loop; // while (bits_left) mov [quot], eax; // quot } return quot; } #else uint32_t bitwise_division (uint32_t dividend, uint32_t divisor) { uint32_t quot, rem, t; int bits_left = CHAR_BIT * sizeof (uint32_t); quot = dividend; rem = 0; do { // (rem:quot) << 1 t = quot; quot = quot + quot; rem = rem + rem + (quot < t); if (rem >= divisor) { rem = rem - divisor; quot = quot + 1; } bits_left--; } while (bits_left); return quot; } #endif 

    Взято отсюда .

    Это только для разделения:

     int add(int a, int b) { int partialSum, carry; do { partialSum = a ^ b; carry = (a & b) << 1; a = partialSum; b = carry; } while (carry != 0); return partialSum; } int subtract(int a, int b) { return add(a, add(~b, 1)); } int division(int dividend, int divisor) { boolean negative = false; if ((dividend & (1 << 31)) == (1 << 31)) { // Check for signed bit negative = !negative; dividend = add(~dividend, 1); // Negation } if ((divisor & (1 << 31)) == (1 << 31)) { negative = !negative; divisor = add(~divisor, 1); // Negation } int quotient = 0; long r; for (int i = 30; i >= 0; i = subtract(i, 1)) { r = (divisor << i); // Left shift divisor until it's smaller than dividend if (r < Integer.MAX_VALUE && r >= 0) { // Avoid cases where comparison between long and int doesn't make sense if (r <= dividend) { quotient |= (1 << i); dividend = subtract(dividend, (int) r); } } } if (negative) { quotient = add(~quotient, 1); } return quotient; } 

    Это должно работать для умножения:

     .data .text .globl main main: # $4 * $5 = $2 addi $4, $0, 0x9 addi $5, $0, 0x6 add $2, $0, $0 # initialize product to zero Loop: beq $5, $0, Exit # if multiplier is 0,terminate loop andi $3, $5, 1 # mask out the 0th bit in multiplier beq $3, $0, Shift # if the bit is 0, skip add addu $2, $2, $4 # add (shifted) multiplicand to product Shift: sll $4, $4, 1 # shift up the multiplicand 1 bit srl $5, $5, 1 # shift down the multiplier 1 bit j Loop # go for next Exit: # EXIT: li $v0,10 syscall 

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

    Код

     -(int)binaryDivide:(int)numerator with:(int)denominator { if (numerator == 0 || denominator == 1) { return numerator; } if (denominator == 0) { #ifdef DEBUG NSAssert(denominator==0, @"denominator should be greater then 0"); #endif return INFINITY; } // if (numerator <0) { // numerator = abs(numerator); // } int maxBitDenom = [self getMaxBit:denominator]; int maxBitNumerator = [self getMaxBit:numerator]; int msbNumber = [self getMSB:maxBitDenom ofNumber:numerator]; int qoutient = 0; int subResult = 0; int remainingBits = maxBitNumerator-maxBitDenom; if (msbNumber >= denominator) { qoutient |=1; subResult = msbNumber - denominator; } else { subResult = msbNumber; } while (remainingBits > 0) { int msbBit = (numerator & (1 << (remainingBits-1)))>0?1:0; subResult = (subResult << 1) | msbBit; if(subResult >= denominator) { subResult = subResult - denominator; qoutient= (qoutient << 1) | 1; } else{ qoutient = qoutient << 1; } remainingBits--; } return qoutient; } -(int)getMaxBit:(int)inputNumber { int maxBit = 0; BOOL isMaxBitSet = NO; for (int i=0; i> (numbeMaxBit - bits); } 

    Для умножения:

     -(int)multiplyNumber:(int)num1 withNumber:(int)num2 { int mulResult = 0; int ithBit; BOOL isNegativeSign = (num1<0 && num2>0) || (num1>0 && num2<0); num1 = abs(num1); num2 = abs(num2); for (int i=0; i0) { mulResult += (num1 << i); } } if (isNegativeSign) { mulResult = ((~mulResult)+1); } return mulResult; } 

    Для всех, кто интересуется 16-разрядным решением x86, здесь есть код JasonKnight здесь (он также включает подписанный множитель, который я не тестировал). Однако этот код имеет проблемы с большими входами, где часть «добавить bx, bx» будет переполняться.

    Фиксированная версия:

     softwareMultiply: ; INPUT CX,BX ; OUTPUT DX:AX - 32 bits ; CLOBBERS BX,CX,DI xor ax,ax ; cheap way to zero a reg mov dx,ax ; 1 clock faster than xor mov di,cx or di,bx ; cheap way to test for zero on both regs jz @done mov di,ax ; DI used for reg,reg adc @loop: shr cx,1 ; divide by two, bottom bit moved to carry flag jnc @skipAddToResult add ax,bx adc dx,di ; reg,reg is faster than reg,imm16 @skipAddToResult: add bx,bx ; faster than shift or mul adc di,di or cx,cx ; fast zero check jnz @loop @done: ret 

    Или же в сборке GCC:

     asm("mov $0,%%ax\n\t" "mov $0,%%dx\n\t" "mov %%cx,%%di\n\t" "or %%bx,%%di\n\t" "jz done\n\t" "mov %%ax,%%di\n\t" "loop:\n\t" "shr $1,%%cx\n\t" "jnc skipAddToResult\n\t" "add %%bx,%%ax\n\t" "adc %%di,%%dx\n\t" "skipAddToResult:\n\t" "add %%bx,%%bx\n\t" "adc %%di,%%di\n\t" "or %%cx,%%cx\n\t" "jnz loop\n\t" "done:\n\t" : "=d" (dx), "=a" (ax) : "b" (bx), "c" (cx) : "ecx", "edi" ); 

    Попробуй это. https://gist.github.com/swguru/5219592

     import sys # implement divide operation without using built-in divide operator def divAndMod_slow(y,x, debug=0): r = 0 while y >= x: r += 1 y -= x return r,y # implement divide operation without using built-in divide operator def divAndMod(y,x, debug=0): ## find the highest position of positive bit of the ratio pos = -1 while y >= x: pos += 1 x <<= 1 x >>= 1 if debug: print "y=%d, x=%d, pos=%d" % (y,x,pos) if pos == -1: return 0, y r = 0 while pos >= 0: if y >= x: r += (1 << pos) y -= x if debug: print "y=%d, x=%d, r=%d, pos=%d" % (y,x,r,pos) x >>= 1 pos -= 1 return r, y if __name__ =="__main__": if len(sys.argv) == 3: y = int(sys.argv[1]) x = int(sys.argv[2]) else: y = 313271356 x = 7 print "=== Slow Version ...." res = divAndMod_slow( y, x) print "%d = %d * %d + %d" % (y, x, res[0], res[1]) print "=== Fast Version ...." res = divAndMod( y, x, debug=1) print "%d = %d * %d + %d" % (y, x, res[0], res[1]) 
    Давайте будем гением компьютера.