Manipulasi bit untuk kelas integer besar?

Saya mengalami masalah dalam membuat algoritma untuk kelas integer besar di C++. Ide awal saya adalah menggunakan array/daftar, tetapi sangat tidak efisien. Saya kemudian menemukan hal-hal seperti kelas berikut: http://www.codeproject.com/KB/cpp/CppIntegerClass.aspx

Namun, menurut saya pendekatan itu sangat membingungkan. Saya tidak tahu cara bekerja dengan manipulasi bit, dan saya hampir tidak memahami kodenya. Seseorang tolong jelaskan kepada saya cara menggunakan manipulasi bit, cara kerjanya, dll. Akhirnya saya ingin membuat kelas integer besar saya sendiri, tapi saya bukan seorang programmer pemula dan saya baru belajar cara menggunakan kelas.

Pada dasarnya pertanyaan saya adalah: Bagaimana cara menggunakan manipulasi bit untuk membuat kelas bilangan bulat besar? Bagaimana cara kerjanya??

Terima kasih!


c++ bit-manipulation biginteger
person Lockhead    schedule 13.12.2010    source sumber

Jawaban (1)


arrow_upward
1
arrow_downward

Mulailah dengan membaca bilangan biner secara umum. Halaman tersebut menunjukkan bagaimana operasi aritmatika umum (penjumlahan, pengurangan, dll) bekerja pada bilangan biner, yaitu bagaimana bilangan tersebut dimanipulasi sedikit demi sedikit untuk mendapatkan hasil yang diinginkan.

Memetakannya ke dalam bahasa pemrograman seperti C++ seharusnya cukup mudah setelah Anda mengetahui mengapa ada operasi manipulasi bit yang digunakan.

Menurut pengalaman saya, hal berorientasi bit yang paling jelas diperlukan ketika mengimplementasikan sesuatu seperti ini adalah pengujian bit, untuk memeriksa overflow. Katakanlah Anda merepresentasikan bilangan biner besar Anda sebagai array uint16_t, yaitu potongan 16 bit. Saat menerapkan penjumlahan, Anda akan memulai dari akhir paling tidak signifikan dari kedua angka, dan menjumlahkannya. Jika jumlahnya lebih besar dari 65.535, Anda perlu "membawa" satu angka ke uint16_t berikutnya, sama seperti saat Anda menjumlahkan angka desimal satu digit dalam satu waktu.

Ini dapat diimplementasikan dengan tes seperti ini:

const uint16_t *number1;
const uint16_t *number2;

/* assume code goes here to set up the number1 and number2 pointers. */

/* Compute sum of 16 bits. */
uint16_t carry = 0;
uint32_t sum = number1[0] + number2[0];

/* One way of testing for overflow: */
if (sum & (1 << 16))
 carry = 1;

Di sini, ekspresi 1 << 16 membuat topeng dengan menggeser 1 enam belas langkah ke kiri. & bitwise dan operator menguji jumlah tersebut terhadap mask; hasilnya akan menjadi bukan nol (yaitu benar, dalam C++) jika bit 16 disetel di sum.

person unwind    schedule 13.12.2010
comment
Namun bukankah hasilnya akan terlalu besar untuk tipe data standar apa pun? Bagaimana cara mengatasinya? - person Lockhead; 13.12.2010