Bagaimana saya bisa mengalikan dan membagi hanya dengan menggeser dan menambahkan sedikit?

86

Bagaimana saya bisa mengalikan dan membagi hanya dengan menggeser dan menambahkan sedikit?

Spidfire
sumber
20
Seperti yang Anda lakukan di atas kertas di sekolah menengah, hanya menggunakan biner, bukan desimal.
Pascal Cuoq
1
@ mtk: Apa yang hilang dari jawaban ini ? Apakah Anda mencari implementasi C atau perakitan, lebar operan tertentu, metode pembagian tertentu (misalnya memulihkan vs non-pemulihan)?
njuffa
Apakah pengurangan OK? Semua tampaknya ditutupi
mksteve
Apa kebutuhan di balik pertanyaan ini? CPU menerjemahkan operasi perkalian dan pembagian menjadi pengalihan bit dan penjumlahan atau pengurangan, dan jika itu terjadi jika kompiler belum melakukannya.
Kelly S. French
1
@ KellyS.French Hanya ingin tahu, ini lebih merupakan cara untuk membayangkan bagaimana kompilator dapat bekerja dengan set instruksi terbatas.
Spidfire

Jawaban:

77

Untuk mengalikan dalam hal penjumlahan dan pergeseran, Anda ingin menguraikan salah satu bilangan dengan pangkat dua, seperti ini:

( _2berarti 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.

Andrew Toulouse
sumber
6
Saya tahu itu beberapa waktu yang lalu, tetapi dapatkah Anda memberi contoh dengan pembagian? Terima kasih
GniruT
42

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?

Viktor Latypov
sumber
Terima kasih banyak atas referensi Delight Hacker!
alecxe
2
Ehm ya, jawaban ini (pembagian dengan konstanta) hanya benar sebagian . Jika Anda mencoba melakukan '3/3', Anda akan berakhir dengan 0. Dalam Hacker's Delight, mereka sebenarnya menjelaskan bahwa ada kesalahan yang harus Anda ganti. Dalam hal ini: b += r * 11 >> 5dengan r = a - q * 3. Tautan: hackersdelight.org/divcMore.pdf halaman 2+.
atlaste
31

X * 2 = 1 bit bergeser ke kiri
X / 2 = 1 bit bergeser ke kanan
X * 3 = geser ke kiri 1 bit lalu tambahkan X

Kelly S. Prancis
sumber
4
Apakah maksud Anda add Xuntuk yang terakhir itu?
Mark Byers
1
Ini masih salah - baris terakhir seharusnya berbunyi: "X * 3 = geser ke kiri 1 bit dan kemudian tambahkan X"
Paul R
1
"X / 2 = 1 bit bergeser ke kanan", tidak seluruhnya, itu membulatkan ke bawah hingga tak terbatas, bukan hingga 0 (untuk bilangan negatif), yang merupakan implementasi pembagian biasa (setidaknya sejauh yang saya lihat).
Leif Andersen
25

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.

IVlad
sumber
@IVlad: Bagaimana Anda akan menggabungkan operasi di atas untuk melakukan, katakanlah, bagi dengan 3?
Paul R
@ Paul R - benar, itu lebih sulit. Saya telah mengklarifikasi jawaban saya.
IVlad
pembagian dengan konstanta tidaklah terlalu sulit (kalikan dengan konstanta ajaib dan kemudian bagi dengan pangkat 2), tetapi pembagian dengan variabel sedikit lebih rumit.
Paul R
1
seharusnya x * 14 == x * 16 - x * 2 == (x << 4) - (x << 2) benar-benar berakhir menjadi (x << 4) - (x << 1) karena x < <1 mengalikan x dengan 2?
Alex Spencer
18
  1. Pergeseran ke kiri sebesar 1 posisi dianalogikan dengan mengalikan dengan 2. Pergeseran kanan dianalogikan dengan membagi dengan 2.
  2. Anda dapat menambahkan satu lingkaran untuk mengalikan. Dengan memilih variabel loop dan variabel penambahan dengan benar, Anda dapat mengikat performa. Setelah Anda menjelajahinya, Anda harus menggunakan Perkalian Petani
Yann Ramin
sumber
9
1: Tapi pergeseran kiri bukan hanya analog dengan mengalikan dengan 2. adalah mengalikan dengan 2. Setidaknya sampai meluap ...
Don Roby
Pembagian shift menghasilkan hasil yang salah untuk bilangan negatif.
David
6

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:

pengguna2954726
sumber
Bagaimana dengan bilangan negatif? Saya menguji -12345 dengan 10 menggunakan eclipse + CDT, tetapi hasilnya tidak terlalu bagus.
kenmux
Bisakah Anda memberi tahu saya mengapa Anda melakukannya ullDivisor >>= 1sebelum whileloop? Juga, tidak akan nPos >= 0berhasil?
Vivekanand V
@kenmux Anda harus mempertimbangkan hanya besarnya angka yang terlibat, pertama, lakukan algoritme dan kemudian gunakan beberapa pernyataan pengambilan keputusan yang sesuai, kembalikan tanda yang tepat ke hasil bagi / sisa!
Vivekanand V
1
@VivekanandV Maksud Anda tambahkan tanda - nanti? Ya, itu berhasil.
kenmux
5

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 .

njuffa
sumber
@greybeard Terima kasih atas penunjuknya, Anda benar, saya mencampur dividen dengan hasil bagi. Saya akan memperbaikinya.
njuffa
4

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:

Jimmeh
sumber
Ini tampaknya tercepat, hanya membutuhkan sedikit pengkodean tambahan untuk mengulang bit-bit dari angka terkecil dan menghitung hasilnya.
Hellonearthis
2

Diambil dari sini .

Ini hanya untuk divisi:

Ashish Ahuja
sumber
2

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

Karim Baidar
sumber
eaxtidak bisa menahan nilai pecahan seperti 1/4. (Kecuali jika Anda menggunakan titik tetap dan bukan bilangan bulat, tetapi Anda tidak menentukannya)
Peter Cordes
1

Ini harus bekerja untuk perkalian:

Melsi
sumber
1
Ini adalah perakitan MIPS, jika ini yang Anda tanyakan. Saya pikir saya menggunakan MARS untuk menulis / menjalankannya.
Melsi
1

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

Untuk perkalian:

menghafalkan
sumber
Apa sintaks ini? -(int)multiplyNumber:(int)num1 withNumber:(int)num2?
SS Anne
0

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:

Atau yang sama dalam perakitan inline GCC:

axic
sumber
-1

Coba ini. https://gist.github.com/swguru/5219592

swguru.net
sumber
5
Ini terlihat seperti python. Pertanyaan diajukan untuk perakitan dan / atau C.
batal