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 Salesman 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-indesk 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 2022). 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 hasil hasilnya.

3. Operasi-operasi manipulasi 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).