Bagaimana saya bisa mengalikan dan membagi hanya dengan menggeser dan menambahkan sedikit?
c
assembly
bit-manipulation
division
multiplication
Spidfire
sumber
sumber
Jawaban:
Untuk mengalikan dalam hal penjumlahan dan pergeseran, Anda ingin menguraikan salah satu bilangan dengan pangkat dua, seperti ini:
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
berarti basis 2)Seperti yang Anda lihat, perkalian dapat diuraikan menjadi menjumlah dan menggeser dan kembali lagi. Ini juga mengapa perkalian membutuhkan waktu lebih lama daripada pergeseran bit atau penambahan - ini adalah O (n ^ 2) daripada O (n) dalam jumlah bit. Sistem komputer nyata (sebagai lawan dari sistem komputer teoretis) memiliki jumlah bit yang terbatas, sehingga perkalian membutuhkan beberapa waktu yang konstan dibandingkan dengan penjumlahan dan pergeseran. Jika saya ingat dengan benar, prosesor modern, jika pipelined dengan benar, dapat melakukan perkalian secepat penambahan, dengan mengacaukan penggunaan ALU (unit aritmatika) di prosesor.
sumber
Jawaban oleh Andrew Toulouse dapat diperluas ke divisi.
Pembagian dengan konstanta integer dibahas secara rinci dalam buku "Hacker's Delight" oleh Henry S. Warren (ISBN 9780201914658).
Ide pertama untuk menerapkan pembagian adalah menuliskan nilai kebalikan dari penyebut di basis dua.
Misalnya,
1/3 = (base-2) 0.0101 0101 0101 0101 0101 0101 0101 0101 .....
Jadi,
a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30)
untuk aritmatika 32-bit.Dengan menggabungkan istilah-istilah dengan cara yang jelas kita dapat mengurangi jumlah operasi:
b = (a >> 2) + (a >> 4)
b += (b >> 4)
b += (b >> 8)
b += (b >> 16)
Ada cara yang lebih menarik untuk menghitung pembagian dan sisa.
EDIT1:
Jika OP berarti perkalian dan pembagian bilangan sembarangan, bukan pembagian dengan bilangan konstan, maka utas ini mungkin bisa digunakan: https://stackoverflow.com/a/12699549/1182653
EDIT2:
Salah satu cara tercepat untuk membagi dengan konstanta integer adalah dengan mengeksploitasi aritmatika modular dan reduksi Montgomery: Apa cara tercepat untuk membagi integer dengan 3?
sumber
b += r * 11 >> 5
denganr = a - q * 3
. Tautan: hackersdelight.org/divcMore.pdf halaman 2+.X * 2 = 1 bit bergeser ke kiri
X / 2 = 1 bit bergeser ke kanan
X * 3 = geser ke kiri 1 bit lalu tambahkan X
sumber
add X
untuk yang terakhir itu?x << k == x multiplied by 2 to the power of k
x >> k == x divided by 2 to the power of k
Anda dapat menggunakan pergeseran ini untuk melakukan operasi perkalian apa pun. Sebagai contoh:
x * 14 == x * 16 - x * 2 == (x << 4) - (x << 1)
x * 12 == x * 8 + x * 4 == (x << 3) + (x << 2)
Untuk membagi angka dengan non-pangkat dua, saya tidak mengetahui cara mudah apa pun, kecuali Anda ingin menerapkan logika tingkat rendah, gunakan operasi biner lain dan gunakan beberapa bentuk iterasi.
sumber
sumber
Saya menerjemahkan kode Python ke C. Contoh yang diberikan memiliki kesalahan kecil. Jika nilai dividen yang mengambil semua 32 bit, pergeseran akan gagal. Saya baru saja menggunakan variabel 64-bit secara internal untuk mengatasi masalah:
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; }
sumber
ullDivisor >>= 1
sebelumwhile
loop? Juga, tidak akannPos >= 0
berhasil?Prosedur untuk membagi bilangan bulat yang menggunakan shift dan penjumlahan dapat diturunkan secara langsung dari pembagian desimal longhand seperti yang diajarkan di sekolah dasar. Pemilihan setiap digit hasil bagi disederhanakan, karena digitnya adalah 0 dan 1: jika sisa saat ini lebih besar dari atau sama dengan pembagi, bit paling signifikan dari hasil bagi parsial adalah 1.
Sama seperti pembagian desimal longhand, digit dividen dianggap dari yang paling signifikan hingga paling tidak signifikan, satu digit pada satu waktu. Ini mudah dilakukan dengan pergeseran kiri dalam pembagian biner. Juga, bit hasil bagi dikumpulkan dengan menggeser bit hasil bagi saat ini dengan satu posisi, lalu menambahkan bit hasil bagi baru.
Dalam aransemen klasik, dua shift kiri ini digabungkan menjadi shift kiri dari satu pasangan register. Setengah bagian atas memegang sisa saat ini, bagian awal bagian bawah memegang dividen. Karena bit dividen ditransfer ke register sisa dengan shift kiri, bit paling signifikan yang tidak terpakai dari bagian bawah digunakan untuk mengakumulasi bit hasil bagi.
Di bawah ini adalah bahasa assembly x86 dan implementasi C dari algoritma ini. Varian khusus dari pembagian geser & tambah ini kadang-kadang disebut sebagai varian "tidak berkinerja", karena pengurangan pembagi dari sisa saat ini tidak dilakukan kecuali jika sisanya lebih besar dari atau sama dengan pembagi. Di C, tidak ada gagasan tentang carry flag yang digunakan oleh versi assembly di shift kiri pasangan register. Sebaliknya justru ditiru, berdasarkan pengamatan bahwa hasil penambahan modulo 2 n bisa lebih kecil baik yang dijumlahkan hanya jika ada pelaksanaan .
#include <stdio.h> #include <stdlib.h> #include <stdint.h> #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
sumber
Ambil dua angka, katakanlah 9 dan 10, tulislah sebagai biner - 1001 dan 1010.
Mulailah dengan hasil, R, dari 0.
Ambil salah satu angka, 1010 dalam hal ini, kita akan menyebutnya A, dan menggesernya sedikit ke kanan, jika Anda menggeser satu, tambahkan nomor pertama, kita akan menyebutnya B, ke R.
Sekarang geser B ke kiri satu bit dan ulangi sampai semua bit bergeser keluar dari A.
Lebih mudah untuk melihat apa yang sedang terjadi jika Anda melihatnya tertulis, ini contohnya:
0 0000 0 10010 1 000000 0 1001000 1 ------ 1011010
sumber
Diambil dari sini .
Ini hanya untuk divisi:
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; }
sumber
itu pada dasarnya mengalikan dan membagi dengan pangkat dasar 2
bergeser ke kiri = x * 2 ^ y
geser ke kanan = x / 2 ^ y
shl eax, 2 = 2 * 2 ^ 2 = 8
menyusut, 3 = 2/2 ^ 3 = 1/4
sumber
eax
tidak bisa menahan nilai pecahan seperti1/4
. (Kecuali jika Anda menggunakan titik tetap dan bukan bilangan bulat, tetapi Anda tidak menentukannya)Ini harus bekerja untuk perkalian:
.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
sumber
Metode di bawah ini adalah penerapan pembagian biner mengingat kedua bilangan tersebut positif. Jika pengurangan menjadi perhatian kita dapat mengimplementasikannya juga menggunakan operator biner.
Kode
-(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<sizeof(inputNumber)*8; i++) { if (inputNumber & (1<<i)) { maxBit = i; isMaxBitSet=YES; } } if (isMaxBitSet) { maxBit+=1; } return maxBit; } -(int)getMSB:(int)bits ofNumber:(int)number { int numbeMaxBit = [self getMaxBit:number]; return number >> (numbeMaxBit - bits); }
Untuk perkalian:
-(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; i<sizeof(num2)*8; i++) { ithBit = num2 & (1<<i); if (ithBit>0) { mulResult += (num1 << i); } } if (isNegativeSign) { mulResult = ((~mulResult)+1); } return mulResult; }
sumber
-(int)multiplyNumber:(int)num1 withNumber:(int)num2
?Bagi siapa pun yang tertarik dengan solusi 16-bit x86, ada sepotong kode oleh JasonKnight di sini 1 (dia juga menyertakan bagian perkalian bertanda tangan, yang belum saya uji). Namun, kode tersebut memiliki masalah dengan input yang besar, di mana bagian "add bx, bx" akan meluap.
Versi tetap:
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
Atau yang sama dalam perakitan inline 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" );
sumber
Coba ini. 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])
sumber