Jarang, tetapi tugas dari wawancara dan pelatihan masih memiliki nilai praktis. Jadi, saya perlu mengimplementasikan di Jawa sebagai alternatif untuk operasi aritmatika pada nilai integer. Untungnya, halaman pertama mesin pencari penuh dengan solusi siap pakai untuk analog bitwise, dan Anda tidak perlu pusing memikirkan kebanyakan dari mereka.
Terus terang, saya agak terkejut dengan kurangnya materi seperti itu di Habré (apakah saya terlihat buruk?), Dan oleh karena itu saya memutuskan untuk mengisi kekurangan ini dengan komentar dan tambahan saya.
Harap perhatikan bahwa dalam contoh dengan operasi bitwise, nilainya dipotong menjadi nibble: tidak akan ada perbedaan mendasar, tetapi lebih mudah dipahami.
Tambahan
Algoritma:
private int add(int summand, int addend)
{
/*.*/
int carry = 0x00;
/* , .*/
while(addend != 0x00)
{
/* .*/
carry = (summand & addend);
/* , .*/
summand = summand ^ addend;
/* .*/
addend = (carry << 1);
}
return summand;
}
Pertama, Anda perlu mengingat tentang transfer ke kategori senior. Dalam sistem desimal, definisinya (untuk digit saat ini) mencakup nilai dalam rentang 10 hingga 18:
109 +
019 =
128
Dalam sistem biner, segala sesuatu yang lebih besar dari satu ditransfer:
0001 +
0001 =
----
0010
atau seperti ini:
0011 +
0011 =
----
0110
Dalam contoh terakhir, bit paling tidak signifikan ditambahkan terlebih dahulu:
1 + 1 = 10 ()
Nol tetap ada di bit saat ini, dan yang satu menuju ke yang paling signifikan, di mana ia berpartisipasi sebagai tambahan:
1 + 1 + 1 = 11 ()
yang paling rendah tetap ada di yang sekarang, yang lebih tua bergerak lebih jauh. Dari sini, Anda dapat menyimpulkan aturan bahwa dalam sistem biner untuk satu bit saat ini, nilai dari dua hingga tiga, inklusif, termasuk dalam carry.
Pada bagian tentang algoritma, perlu memperhatikan instruksi untuk menentukan ada / tidaknya transfer menggunakan contoh nilai sebelumnya:
carry = (summand & addend);
0011 = 0011 & 0011
Ini bukan transfer, tetapi pengaturan "bendera" di atas digit, yang penambahannya meninggalkan transfer, yaitu add carry adalah saat bitnya sama.
Segera setelah sesuatu menjadi jelas, sekarang istilah pertama harus dibebaskan dari bit yang transfernya diperhitungkan:
summand = summand ^ addend;
0000 = 0011 ^ 0011
Seperti yang Anda ketahui, operator XOR bitwise akan menyetel bit hanya jika nilai bitnya berlawanan.
Langkah ketiga dalam loop adalah mengubah bendera carry secara langsung menjadi carry. Untuk melakukan ini, mereka digeser satu langkah ke kiri dan ditugaskan ke suku kedua:
addend = (carry << 1);
0110 = (0011 << 1);
Pada iterasi berikutnya, transfer tidak akan diperbaiki, karena:
carry = (summand & addend);
0000 = 0000 & 0110
Langkah kedua akan memberi kita:
summand = summand ^ addend;
0110 = 0000 ^ 0110,
Yang mana jumlah yang diinginkan, dan langkah ketiga akan mengakhiri perulangan while ():
addend = (carry << 1);
0000 = (0000 << 1)
Pengurangan
Algoritma:
private int sub(int minuend, int subtrahend)
{
/* .*/
int borrow = 0x00;
/* , .*/
while(subtrahend != 0x00)
{
/* .*/
borrow = ((~minuend) & subtrahend);
/* , .*/
minuend = minuend ^ subtrahend;
/* .*/
subtrahend = (borrow << 1);
}
return minuend;
}
Setara dengan yang sebelumnya, dengan satu-satunya perbedaan bahwa peminjaman bit dari bit paling signifikan diimplementasikan inversi implikasi terbalik . Nah, kami mengganti nama variabel lokal.
Perkalian
Algoritma:
public int multiply(int mul1, int mul2)
{
int result = 0;
/* .*/
while(mul2 != 0)
{
/* ...*/
if ((mul2 & 1) == 1)
{
/* .*/
result = add(result, mul1);
}
/* ("")*/
mul1 <<= 1;
/* if()*/
mul2 >>>= 1;
}
return result;
}
Kembali ke dasar: perkalian panjang dalam sistem desimal:
25 *
05 =
--
125 +
00
---
125
itu. kami mengalikan setiap digit faktor kedua dengan faktor pertama. Dari sini dapat disimpulkan bahwa produk dari bit paling signifikan digeser satu langkah ke kiri. Terakhir, tambahkan nilai antara. Hal yang sama terjadi pada level bitwise:
0110 *
0011 =
----
0110 +
0 110 +
00 00 +
000 0 +
- ----
1 0010
Kami menyimpulkan bahwa algoritme hanya perlu, bahwa menambahkan faktor pertama ke dirinya sendiri setiap kali bit set ditemukan di faktor kedua, tentu saja, dengan mempertimbangkan aturan untuk mentransfer ke bit yang paling signifikan:
if ((mul2 & 1) == 1) //(0011 & 0001) == 0001
{
result = add(result, mul1); //0110 = 0000 + 0110
}
Kemudian pengali pertama digeser sedikit ke kiri (kita membentuk "tangga"):
mul1 <<= 1; //1100 = 0110 << 1;
Sekarang kami menentukan apakah ada bit di bit paling signifikan kedua dari faktor kedua:
mul2 >>>= 1; //0001 = 0011 >>> 1;
Siklus berjalan hingga faktor kedua nol. Saya ingin menarik perhatian Anda pada hal-hal berikut: sebuah instance dari algoritma ini berjalan dari sumber daya ke sumber daya, di mana pergeseran logis dari faktor kedua (mul2 >>> = 1) digantikan oleh aritmatika (mul2 >> = 1) . Ini mungkin berasal dari implementasi di C / C ++, di mana ada kata kunci unsigned dan substitusi semacam itu tidak menjadi masalah. Namun, di Java semua jenis angka ditandatangani, dan jika faktor kedua diwakili oleh nilai negatif, maka kekeliruan seperti itu akan menyebabkan algoritme jatuh ke loop tak terbatas, karena faktor kedua akan selalu memenuhi kondisinya:
1000 >>1; //
1100 >>1; // ( 0100)
1110 >>1; // 0010
1111 >>1; // -1
Divisi
Algoritma:
private int divide(int dividend, int divisor)
{
/*, .*/
int quotient = 0x00, mask = 0x01;
/* .*/
int temp = divisor;
/* .*/
int sign = ((dividend < 0)^(divisor < 0)) ? sign = -1 : 1;
/* .*/
dividend = dividend < 0 ? add((~dividend), 1) : dividend;
divisor = divisor < 0 ? add((~divisor), 1) : divisor;
/* 0 .*/
if (dividend < divisor) return quotient;
while(dividend > 0 || divisor != 0)
{
/* .*/
if ((dividend >= (divisor << 0x01)) && ((divisor << 0x01) > 0))
{
divisor <<= 0x01;
mask <<= 0x01;
}
/* .*/
else
{
/* "" .*/
quotient = quotient | mask;
/* .*/
dividend = sub(dividend, divisor);
/* .*/
divisor = temp;
mask = 0x01;
}
}
return multiply(quotient, sign);
}
Pembagian ini tidak berjalan mulus seperti contoh sebelumnya: Saya harus menulis sepeda (tidak terkena pukulan keras).
Pembagian adalah pengurangan pembagi dari pembagi selama hasil bagi lebih besar dari atau sama dengan nol. Dengan pendekatan ini, cukup mendefinisikan penghitung, yang nilainya bertambah setelah setiap operasi pengurangan. Nilai akhirnya adalah yang khusus:
count = 0;
1) 7 - 3 = 4; count = 1;
2) 4 - 3 = 1; count = 2;
7 / 3 = count;
Kerugian dari pendekatan ini menjadi sangat terlihat ketika memasok perangkat dengan sumber daya terbatas dari urutan instruksi, seperti: 2147483647/1; 2147483647/2; 2147483647/3 , sepertinya aplikasi macet.
Bekerja pada tingkat bit akan jauh lebih efisien. Tetapi satu-satunya solusi yang ditemukan memiliki kelemahan yaitu untuk inferensi yang benar, jenis variabel diperlukan, satu langkah di atas kisaran yang dicakup, yaitu. jika input pendek , maka jenis variabel lokal harus int , jika tidak, hasil pembagian nilai besar akan mengejutkan. Dalam kasus saya, situasinya diperparah dengan tidak adanya tipe panjang.
Tapi kembali ke domba jantan kami.
Untuk memahami prinsip algoritme, Anda perlu mengingat urutan pembagian berdasarkan kolom:
= 6, = 2;
0110|0010
----
110|10 //
, , :
1) (1 >= 10) -> ,
110|10
--
0
2) (11 >= 10) -> ,
110|10
-10 --
-- 01
01
Di sini lebih detail. Di knalpot, kami mendapatkan yang berikut: kami "mendorong" pembatas ke kiri hingga pembuangan di mana itu meminimalkan perbedaan dengan yang dapat dibagi:
2.1) 0110 / 0010 -> 0110 - 0100 = 0010 = 2.
3) (10 >= 10) -> ,
110|10
-10 --
-- 011
010
-10
--
00
Mekanisme ini diimplementasikan dalam algoritma. Dalam perulangan while (), pembagi harus digeser ke kiri hingga memenuhi aturan di atas. Sejalan dengan itu, private mask digeser. Operator percabangan if () mengatakan: "Anda dapat menggeser jika hanya hasil dari operasi ini yang tidak melanggar aturan dasar." Pemeriksaan tambahan untuk angka negatif disebabkan oleh fakta bahwa kumpulan bit paling signifikan di Jawa adalah angka negatif. Tanpanya, siklus akan jatuh hingga tak terbatas:
//((divisor << 0x01) > 0) ,
1) 0111 >= 0010<<1
2) 0111 >= 0100<<1
3) 0111 >= 1000<<1 //! - if() , , .
4) 0111 >= 0000<<1
....
Segera setelah algoritme berhenti memenuhi syarat if (), kode tersebut memasuki else, di mana bit mask disetel pada hasil bagi:
quotient = quotient | mask;
0010 = 0000 | 0010
Ini sama dengan mengatur bit untuk pembagian panjang. Kemudian pembagi dikurangi dari dividen:
dividend = sub(dividend, divisor);
0010 = 0110 - 0100
Setelah itu, pembagi dan topeng kembali ke keadaan semula dan siklus dimulai lagi:
divisor = temp;
mask = 0x01;
Terakhir, saya ingin menambahkan beberapa kata tentang kode tambahan.
Algoritma di atas mengasumsikan pembagian hanya dari bilangan positif yang diperoleh dengan kode komplementer:
dividend = dividend < 0 ? add((~dividend), 1) : dividend;
divisor = divisor < 0 ? add((~divisor), 1) : divisor;
Di sini hal berikut terjadi: jika angkanya negatif, maka bitnya dibalik, dan hasilnya ditambahkan dengan satu dan kita mendapatkan nilai positif (absolut). Aturan yang sama berlaku untuk bilangan positif, misalnya:
6 = 0110 -> ~6 = 1001 = 1001 + 1 = 1010 = -6
-6 = 1010 -> ~-6 = 0101 = 0101 + 1 = 0110 = 6
Tetapi ada satu pengecualian - ini adalah bilangan negatif terbesar dari jenis tertentu, misalnya:
int -2147483648 ->
~1000 0000 0000 0000 0000 0000 0000 0000 =
0111 1111 1111 1111 1111 1111 1111 1111 + 1 =
1000 0000 0000 0000 0000 0000 0000 0000.
Hati-hati.