Masker Bit

1. Introduction

Masker Bit menyediakan cara yang efisien untuk memanipulasi sebuah himpunan Boolean kecil yang disimpan sebagai bilangan bulat bertanda 32 (atau 64) bit dalam basis-10 tetapi diterjemahkan sebagai sebuah string pendek dengan 32 (atau 64) karakter.


Dengan menggunakan operasi-operasi manipulasi bit, setiap bit dapat dicek, dinyalakan (atau dimatikan) dengan mudah dan cepat. Masker Bit bisa digunakan didalam berbagai algoritma-algoritma seperti solusi Pemrograman Dinamis untuk Travelling Salesperson Problem untuk mempercepat operasi-operasi himpunan (kecil) yang krusial.

2. Visualisasi

Visualisasi dari struktur data masker bit dan operasi-operasinya diperlihatkan diatas.


Baris paling atas medeskripsikan indeks-indeks dari bit-bit dari bilangan bulat masukan S dimulai dari bit ke-0 sebagai bit paling kanan. Catat bahwa kami menggunakan notasi heksadesimal 1 digit A/B/../E untuk bit ke 10/11/../14.


Baris kedua mendeskripsikan bit-bit dari bilangan bulat masukan S. Dalam aplikasi-aplikasi praktis, ini biasanya sebuah bilangan bulat bertanda 32-bit (misalkan int dalam C++/kebanyakan bahasa-bahasa pemrograman lainnya di tahun 2023). Kadang-kadang, ini adalah bilangan bulat bertanda 64-bit (misalkan long long dalam C++). Untuk visualisasi ini, kami membatasi S sebagai bilangan bulat bertanda 16-bit.

Baris ketiga mendeskripsikan bits-bits dari masker (bit) yang akan diaplikasikan ke S bersama dengan operasi manipulasi bit yang bersangkutan.

Baris terakhir mendeskripsikan hasilnya.

3. Operasi-operasi masker bit

Dalam visualisasi ini, kami saat ini mendukung 6 operasi masker bit (semua berjalan dalam O(1)):

  1. Set S (beberapa cara)
  2. Set Bit ke-j
  3. Cek Bit ke-j
  4. Ubah Bit ke-j
  5. Clear Bit ke-j
  6. Bit Aktif Paling Kanan

3-1. Set S

Kita bisa memasukkan sebuah bilangan bulat (kecil) diantara [0..32767 (215-1)] dalam Desimal (basis-10) dan bentuk Biner (basis-2) dari S akan divisualisasikan.


Alternatifnya, kita bisa memilh bilangan bulat acak diantara jangkauan yang sama [0..32767], sebuah pangkat 2 acak (dengan pola spesifik '10...0'), atau sebuah pangkat 2 acak dikurangi satu (dengan pola spesifik '11...1').

3-2. Nyalakan Bit ke-j

Kita bisa memasukkan indeks dari Bit ke-j dari S untuk diset (dinyalakan).


Catat bahwa indek dimulai dari 0 tetapi dihitung dari bit yang paling kanan (lihat baris paling atas).


Operasi manipulasi bitnya sederhana: S OR (1 << j).


Menyalakan bit yang sudah menyala tidak akan mengubah apapun.

3-3. Cek Bit ke-j

Kita bisa memasukkan indeks dari Bit ke-j dari S untuk dicek (apakah nyala atau mati).


Catat bahwa indek dimulai dari 0 tetapi dihitung dari bit yang paling kanan (lihat baris paling atas).


Operasi manipulasi bitnya sederhana: S AND (1 << j).

3-4. Hapus Bit ke-j

Kita bisa memasukkan indeks dari Bit ke-j dari S untuk dihapus (dimatikan).


Catat bahwa indek dimulai dari 0 tetapi dihitung dari bit yang paling kanan (lihat baris paling atas).


Operasi manipulasi bitnya sederhana: S AND ~(1 << j).


Menghapus bit yang sudah mati tidak akan mengubah apapun.

3-5. Ubah Bit ke-j

Kita bisa memasukkan indeks dari Bit ke-j dari S untuk diubah (nyala → mati atau mati → nyala).


Catat bahwa indek dimulai dari 0 tetapi dihitung dari bit yang paling kanan (lihat baris paling atas).


Operasi manipulasi bitnya sederhana: S XOR (1 << j).

3-6. Bit Aktif Paling Kanan

Operasi ini tidak membutuhkan masukan. Ini adalah operasi spesial untuk dengan cepat mengidentifikasikan bit terkanan yang menyala dalam S.


Operasi manipulasi bitnya sederhana: S AND (-S).


Catat bahwa didalam Two's complement, -S = NOT(S)+1.

4. Tantangan-tantangan

Untuk contoh source code mengenai masker bit/manipulasi bit, silahkan menganalisa: bit_manipulation.cpp | py | java | ml.


Untuk menguji pemahaman anda mengenai manipulasi bit, cobalah Kuis Online topik masker bit kami.


Dan untuk untuk masalah-masalah yang lebih menantang mengenai masker bit/manipulasi bit, cobalah masalah-masalah online judge: Uva 11933 - Splitting Numbers dan Kattis - bitbybit.


Diluar aplikasi-aplikasi mudah ini, manipulasi bit biasanya digunakan sebagai optimisasi level-rendah di berbagai algoritma-algoritma tingkat lanjut, jadi bersiaplah jika anda menjumpai manipulasi bit sebagai sub-komponen dari algoritma-algoritma yang lebih besar.