Masker Bit: Set, Clear, Toggle, Check
Implementasikan fungsi pembantu untuk mengatur, menghapus, membalik, dan memeriksa bit individual, lalu terapkan masker bit untuk merepresentasikan himpunan bagian dalam masalah enumerasi himpunan bagian
Masker Bit: Set, Clear, Toggle, Check adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa Itu Mask Bit?
Mask bit adalah bilangan bulat yang digunakan untuk memilih, mengubah, atau menguji bit tertentu dalam bilangan bulat lain. Mask tersebut memiliki angka 1 pada posisi yang Anda perlukan dan angka 0 di posisi lainnya. Jika digabungkan dengan operator bit, mask memungkinkan Anda melakukan operasi bit yang terperinci tanpa memengaruhi bit lain.
Empat operasi mask dasar adalah: pengaturan (menyalakan bit), penghapusan (mematikan bit), pembalikan (membalik bit), dan pemeriksaan (menguji apakah bit bernilai 1). Masing-masing menggunakan operator yang berbeda—OR, AND-NOT, XOR, dan AND—dengan mask 1 << k.
# The four fundamental bit mask operations
def set_bit(n, k): return n | (1 << k) # OR to set
def clear_bit(n, k): return n & ~(1 << k) # AND-NOT to clear
def toggle_bit(n, k): return n ^ (1 << k) # XOR to toggle
def check_bit(n, k): return (n >> k) & 1 # shift+AND to check
n = 0b10110101 # 181
print(f'n = {bin(n)}')
print(f'set bit 1: {bin(set_bit(n, 1))}')
print(f'clear bit 2: {bin(clear_bit(n, 2))}')
print(f'toggle bit 0: {bin(toggle_bit(n, 0))}')
print(f'check bit 4: {check_bit(n, 4)}')Mengatur Bit: Menyalakan Bit
Untuk mengatur bit k (memaksanya menjadi 1 berapa pun nilainya saat ini), lakukan OR terhadap bilangan dengan mask 1 << k. Karena 0 OR 1 = 1 dan 1 OR 1 = 1, bit target menjadi 1. Semua bit lainnya dikenai OR dengan 0, sehingga tidak berubah.
Pengaturan bit bersifat idempoten—menerapkannya beberapa kali memberikan efek yang sama seperti menerapkannya sekali. Jika bit k sudah bernilai 1, hasilnya tidak berubah. Sifat ini penting untuk pengelolaan penanda ketika Anda ingin mengaktifkan suatu fitur tanpa mengkhawatirkan keadaannya saat ini.
def set_bit(n, k):
mask = 1 << k
return n | mask
# Set various bits
n = 0b00001010 # 10
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
result = set_bit(n, k)
print(f'Set bit {k}: {bin(result)} = {result}')
# Idempotence: setting already-set bit does nothing
n = 0b1111
print(f'\nAlready set: {bin(set_bit(n, 2))} = {bin(n)} (unchanged)')
# Setting multiple bits at once with a combined mask
mask = (1 << 0) | (1 << 2) | (1 << 4) # bits 0, 2, 4
print(f'Set bits 0,2,4: {bin(0 | mask)} = {0 | mask}')Menghapus Bit: Mematikan Bit
Untuk menghapus bit k (memaksanya menjadi 0 berapa pun nilainya saat ini), lakukan AND terhadap bilangan dengan komplemen mask: n & ~(1 << k). Komplemen ~(1 << k) memiliki semua bit bernilai 1 kecuali bit k, yang bernilai 0. AND dengan 0 memaksa bit target menjadi 0; AND dengan 1 mempertahankan semua bit lainnya.
Seperti pengaturan, penghapusan bersifat idempoten. Menghapus bit yang sudah bernilai 0 tidak mengubah bilangan. Dalam Python, ~(1 << k) bekerja dengan benar untuk k berapa pun karena Python menangani ekstensi tanda secara otomatis—secara konseptual, komplemen tersebut memiliki semua bit yang lebih tinggi bernilai 1.
def clear_bit(n, k):
mask = ~(1 << k) # all 1s except bit k
return n & mask
n = 0b11111111 # 255: all bits set
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
result = clear_bit(n, k)
print(f'Clear bit {k}: {bin(result)} = {result}')
# Clear multiple bits with combined mask complement
def clear_bits(n, positions):
mask = 0
for k in positions:
mask |= (1 << k)
return n & ~mask
result = clear_bits(0b11111111, [1, 3, 5, 7])
print(f'Clear bits 1,3,5,7: {bin(result)} = {result}') # 0b01010101 = 85Membalik Bit: Mengubah Nilai Bit
Untuk membalik bit k (mengubahnya dari 0 menjadi 1 atau dari 1 menjadi 0), lakukan XOR terhadap bilangan dengan mask 1 << k. XOR dengan 1 membalik bit; XOR dengan 0 tidak mengubahnya. Inilah sifat dasar XOR yang diterapkan pada satu bit.
Pembalikan adalah satu-satunya dari empat operasi yang tidak idempoten—menerapkannya dua kali mengembalikan nilai semula. Hal ini membuatnya sempurna untuk fitur yang berganti-ganti antara dua keadaan, seperti sakelar hidup/mati atau penanda benar/salah dalam representasi bilangan bulat yang ringkas.
def toggle_bit(n, k):
return n ^ (1 << k)
n = 0b10101010 # 170
print(f'Original: {bin(n)}')
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}') # off->on: 10101011
print(f'Toggle bit 1: {bin(toggle_bit(n, 1))}') # on->off: 10101000
print(f'Toggle bit 7: {bin(toggle_bit(n, 7))}') # on->off: 00101010
# Toggle is its own inverse: two toggles = no change
result = toggle_bit(toggle_bit(n, 3), 3)
print(f'Double toggle bit 3: {bin(result)} == original {bin(n)}? {result == n}')
# Toggle all lower k bits
def toggle_lower_k(n, k):
mask = (1 << k) - 1 # k ones in the lowest positions
return n ^ mask
print(f'Toggle lower 4 bits of {bin(n)}: {bin(toggle_lower_k(n, 4))}')Memeriksa Bit: Menguji Apakah Bit Bernilai 1
Untuk memeriksa apakah bit k bernilai 1, geser n ke kanan sebanyak k posisi, lalu lakukan AND dengan 1: (n >> k) & 1. Ini membawa bit k ke posisi 0 dan meniadakan semua bit yang lebih tinggi, sehingga tersisa 0 (bit k bernilai 0) atau 1 (bit k bernilai 1). Alternatifnya, gunakan bool(n & (1 << k)) untuk mendapatkan hasil benar/salah.
Pemeriksaan bit tidak merusak data—operasi ini tidak mengubah n. Anda dapat memeriksa beberapa bit dengan menggeser dan menerapkan mask pada setiap posisi secara terpisah. Inilah dasar untuk mengiterasi representasi bit suatu bilangan, yang digunakan dalam enumerasi himpunan bagian dan pemrograman dinamis dengan keadaan mask bit.
def check_bit(n, k):
return (n >> k) & 1
def is_bit_set(n, k):
return bool(n & (1 << k))
n = 0b10110101 # 181
print(f'n = {bin(n)} = {n}')
for k in range(8):
print(f'Bit {k}: {check_bit(n, k)} ({"set" if check_bit(n, k) else "clear"})')
# Count set bits using check_bit
def count_set_bits(n):
return sum(check_bit(n, k) for k in range(n.bit_length()))
print(f'\nSet bits in {n}: {count_set_bits(n)}')
# Get bit representation as list (LSB first)
def to_bit_list(n, width=8):
return [check_bit(n, k) for k in range(width)]
print(f'Bit list (LSB first): {to_bit_list(n)}')Mask Bit untuk Representasi Himpunan Bagian
Bilangan bulat dengan n bit dapat merepresentasikan himpunan bagian dari himpunan beranggotakan n elemen: bit k bernilai 1 jika elemen k ada dalam himpunan bagian, dan 0 jika tidak. Cara ini memadatkan sebuah himpunan bagian menjadi satu bilangan bulat, sehingga memungkinkan operasi O(1): pemeriksaan keanggotaan (mask & (1 << k)), menambahkan elemen (mask | (1 << k)), menghapus elemen (mask & ~(1 << k)), serta gabungan/irisan himpunan (mask1 | mask2 dan mask1 & mask2).
Dengan n elemen, terdapat 2^n himpunan bagian yang mungkin, dan masing-masing direpresentasikan secara unik oleh bilangan bulat dengan n bit dari 0 hingga 2^n - 1. Mengiterasi semua bilangan bulat dari 0 hingga 2^n - 1 akan mencacah semua himpunan bagian.
# Subset representation with bitmasks
elements = ['A', 'B', 'C', 'D']
n = len(elements)
def subset_from_mask(mask):
return [elements[k] for k in range(n) if (mask >> k) & 1]
# Enumerate all 2^n subsets
print('All subsets:')
for mask in range(1 << n): # 0 to 15 for n=4
print(f' {mask:04b}: {subset_from_mask(mask)}')
# Set operations
mask_ab = 0b0011 # {A, B}
mask_bc = 0b0110 # {B, C}
print(f'\nUnion: {subset_from_mask(mask_ab | mask_bc)}')
print(f'Intersection: {subset_from_mask(mask_ab & mask_bc)}')
print(f'Difference A\\B: {subset_from_mask(mask_ab & ~mask_bc & 0b1111)}')Mengiterasi Semua Himpunan Bagian dari Sebuah Mask Bit
Dalam pemrograman dinamis berbasis mask bit, Anda sering perlu mengiterasi semua himpunan bagian dari mask tertentu. Trik umum: mulai dengan sub = mask dan lakukan iterasi menggunakan sub = (sub - 1) & mask sampai sub mencapai 0. Setiap iterasi menghasilkan mask bagian yang berbeda. Kompleksitas totalnya adalah O(3^n) untuk semua mask karena setiap elemen dapat berada dalam mask luar tetapi tidak dalam mask bagian, berada dalam keduanya, atau tidak berada dalam keduanya.
Teknik ini muncul dalam masalah seperti ‘membagi larik menjadi himpunan bagian dengan XOR yang sama’ atau ‘menemukan AND maksimum dari sembarang himpunan bagian’. Kemampuan untuk mencacah mask bagian secara efisien merupakan ciri khas DP mask bit tingkat lanjut.
def all_submasks(mask):
submasks = []
sub = mask
while sub > 0:
submasks.append(sub)
sub = (sub - 1) & mask
submasks.append(0) # empty subset
return submasks
mask = 0b1011 # {0, 1, 3}
elements = ['A', 'B', 'C', 'D']
def show(m): return '{' + ','.join(elements[k] for k in range(4) if (m>>k)&1) + '}'
print(f'All submasks of {bin(mask)} = {show(mask)}:')
for sub in all_submasks(mask):
print(f' {bin(sub):6s}: {show(sub)}')
print(f'Total: {len(all_submasks(mask))} submasks (should be 2^{bin(mask).count("1")} = {2**bin(mask).count("1")})')DP Masker Bit: Pratinjau Persoalan Pedagang Keliling
DP masker bit menyelesaikan persoalan ketika keadaan mencakup himpunan bagian elemen yang telah dikunjungi. Contoh klasiknya adalah Persoalan Pedagang Keliling (TSP): temukan tur berbiaya minimum yang mengunjungi n kota. Keadaannya adalah dp[mask][city] = biaya minimum untuk mengunjungi kota-kota dalam mask, dengan akhir di city. Dengan n kota, terdapat 2^n × n keadaan, sehingga waktu O(n^2 × 2^n) — layak untuk n ≤ 20.
Masker berfungsi sebagai himpunan kunjungan yang dipadatkan. Menyetel, menghapus, dan memeriksa bit bersesuaian dengan mengunjungi, meninggalkan, dan menanyakan kota. Inilah inti DP masker bit: gunakan bit sebagai himpunan ringkas untuk keadaan.
# TSP with bitmask DP
import sys
def tsp(dist):
n = len(dist)
INF = float('inf')
# dp[mask][v] = min cost to reach v having visited cities in mask
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # start at city 0, only city 0 visited (mask=1=0b0001)
for mask in range(1 << n):
for v in range(n):
if dp[mask][v] == INF: continue
if not (mask >> v) & 1: continue # v must be in mask
for u in range(n):
if (mask >> u) & 1: continue # u must not be visited
new_mask = mask | (1 << u)
dp[new_mask][u] = min(dp[new_mask][u], dp[mask][v] + dist[v][u])
full_mask = (1 << n) - 1
return min(dp[full_mask][v] + dist[v][0] for v in range(1, n))
dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
print('TSP minimum tour cost:', tsp(dist)) # should be 80Masking Multi-bit: Mengekstrak Bagian
Terkadang Anda perlu mengekstrak bukan hanya satu bit, melainkan bagian multi-bit — rentang bit yang berurutan. Untuk mengekstrak bit dari posisi start hingga start+length-1, buat masker yang terdiri dari length bit 1 berurutan: mask = (1 << length) - 1, lalu gunakan (n >> start) & mask.
Teknik ini digunakan saat mengurai format bilangan bulat terkemas, seperti alamat IP, data piksel, atau register perangkat keras, yang menyimpan beberapa nilai kecil dalam satu bilangan bulat. Sebagai contoh, piksel RGB565 16-bit menyimpan warna merah pada bit 15-11, hijau pada 10-5, dan biru pada 4-0.
def extract_field(n, start, length):
mask = (1 << length) - 1 # e.g., length=3 => mask=0b111
return (n >> start) & mask
# RGB565 pixel format: RRRRRGGGGGGBBBBB
pixel = 0b1111100111001000 # 63432
red = extract_field(pixel, 11, 5) # bits 15-11
green = extract_field(pixel, 5, 6) # bits 10-5
blue = extract_field(pixel, 0, 5) # bits 4-0
print(f'Pixel: {hex(pixel)}')
print(f'Red: {red} ({bin(red)})')
print(f'Green: {green} ({bin(green)})')
print(f'Blue: {blue} ({bin(blue)})')
# Packing values back
def pack_rgb565(r, g, b):
return (r << 11) | (g << 5) | b
packe = pack_rgb565(red, green, blue)
print(f'Repacked: {hex(packed) if (packed := pack_rgb565(red,green,blue)) else 0}')Masker Bit dalam Persoalan Wawancara
Masker bit umum muncul dalam jenis persoalan wawancara berikut:
- Enumerasi himpunan bagian: iterasikan semua 2^n himpunan bagian menggunakan masker 0 hingga 2^n-1
- DP kompresi keadaan: enkode himpunan simpul atau elemen yang telah dikunjungi sebagai masker bit dalam keadaan DP
- Sistem izin: gabungkan penanda READ/WRITE/EXECUTE dengan OR, lalu periksa dengan AND
- Pelacakan kunjungan pada kisi: untuk kisi kecil, kemas sel yang telah dikunjungi ke dalam satu bilangan bulat
Indikator utama bahwa masker bit berguna adalah persoalan melibatkan himpunan kecil (n ≤ 20 elemen) dan Anda perlu melacak kombinasi keanggotaan. Himpunan yang lebih besar memerlukan representasi berbeda.
# Subset sum with bitmask enumeration
def subset_sum_exists(nums, target):
n = len(nums)
for mask in range(1 << n):
total = sum(nums[k] for k in range(n) if (mask >> k) & 1)
if total == target:
subset = [nums[k] for k in range(n) if (mask >> k) & 1]
print(f'Found subset {subset} summing to {target}')
return True
return False
subset_sum_exists([3, 1, 4, 1, 5], 10) # finds a subset summing to 10
# Check if permutation covers all required elements (bitmask approach)
required = 0b11111 # need all 5 elements
visited = 0b01101 # visited elements 0, 2, 3
all_visited = (visited & required) == required
print(f'All required visited: {all_visited}') # False: missing bits 1 and 4Trik Enumerasi Bit yang Efisien
Saat menelusuri bit-bit yang disetel dalam sebuah masker, dua teknik umum dapat digunakan. Metode geser-dan-periksa: geser ke kanan dan periksa LSB. Metode isolasi bit yang disetel paling rendah: isolasikan bit yang disetel paling rendah dengan n & -n, proses bit tersebut, lalu hapus dengan n &= n - 1. Metode kedua hanya mengunjungi bit yang disetel dan lebih cepat ketika masker jarang terisi.
Dalam Python, Anda juga dapat menggunakan bin(n).count('1') atau n.bit_count() (3.10+) untuk menghitung jumlah bit 1. Untuk posisi bit dari setiap bit yang disetel, gunakan n.bit_length() - 1 untuk bit tertinggi yang disetel.
# Iterate over set bit positions
def set_bit_positions(n):
positions = []
k = 0
while n:
if n & 1:
positions.append(k)
n >>= 1
k += 1
return positions
# Faster: use lowest-set-bit isolation
def set_bit_positions_fast(n):
positions = []
while n:
lsb = n & -n # isolate lowest set bit
k = lsb.bit_length() - 1 # position of that bit
positions.append(k)
n &= n - 1 # clear lowest set bit
return positions
mask = 0b10110101
print(f'Set positions (naive): {set_bit_positions(mask)}')
print(f'Set positions (fast): {set_bit_positions_fast(mask)}')
print(f'Bit count: {bin(mask).count("1")}')
print(f'Highest set bit: {mask.bit_length() - 1}')Pemeriksaan Cepat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda telah mempelajari: the empat operasi dasar masker bit adalah setel (OR), hapus (AND-NOT), balik (XOR), dan periksa (geser-AND), bilangan bulat dapat merepresentasikan himpunan bagian dengan setiap bit mengodekan keanggotaan satu elemen, sehingga memungkinkan enumerasi 2^n himpunan bagian, dan ekstraksi bagian multi-bit serta DP masker bit menggunakan prinsip pemaskeran yang sama untuk pengodean keadaan yang lebih kompleks. Berikutnya kita akan membahas penghitungan bit, bilangan yang hilang, dan pembalikan bit menggunakan teknik dari pelajaran ini dan pelajaran sebelumnya.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Masker Bit: Set, Clear, Toggle, Check” gratis?
Ya — teks lengkap “Masker Bit: Set, Clear, Toggle, Check” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Masker Bit: Set, Clear, Toggle, Check”?
Implementasikan fungsi pembantu untuk mengatur, menghapus, membalik, dan memeriksa bit individual, lalu terapkan masker bit untuk merepresentasikan himpunan bagian dalam masalah enumerasi himpunan ba… Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Masker Bit: Set, Clear, Toggle, Check” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Operator Bitwise: AND, OR, XOR, NOT, Pergeseran
- Single Number dan Sifat XOR
- Masker Bit: Set, Clear, Toggle, Check
- Menghitung Bit, Angka yang Hilang, dan Membalik Bit