0Pricing
Coding Interview Prep · Pelajaran

Operator Bitwise: AND, OR, XOR, NOT, Pergeseran

Tinjau keenam operator bitwise dengan tabel kebenaran dan contoh Python, lalu pahami hubungan pergeseran kiri/kanan dengan perkalian dan pembagian dua

Operator Bitwise: AND, OR, XOR, NOT, Pergeseran adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 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.

Mengapa Manipulasi Bit Penting

Manipulasi bit memungkinkan Anda mengoperasikan representasi biner bilangan bulat secara langsung. Banyak masalah yang tampak rumit menjadi sepele dengan trik operasi bit yang tepat: menemukan bilangan yang hilang dalam waktu O(n) dan ruang O(1), menukar variabel tanpa variabel sementara, atau menyandikan himpunan bagian secara ringkas. Pewawancara menggunakan masalah ini untuk menguji pemahaman tingkat rendah dan pemikiran kreatif.

Bilangan bulat Python memiliki presisi tak terbatas—ukurannya dapat sebesar apa pun selama kapasitas memori memungkinkan—tetapi operasi bit selalu mengikuti semantik komplemen dua standar pada tingkat perangkat keras. Keenam operator bekerja pada representasi biner bilangan bulat bit demi bit.

# All six bitwise operators in Python
a, b = 0b1010, 0b1100  # 10 and 12 in decimal
print(f'a = {bin(a)} = {a}')
print(f'b = {bin(b)} = {b}')
print(f'a & b  (AND) = {bin(a & b)} = {a & b}')   # 1000 = 8
print(f'a | b  (OR)  = {bin(a | b)} = {a | b}')   # 1110 = 14
print(f'a ^ b  (XOR) = {bin(a ^ b)} = {a ^ b}')   # 0110 = 6
print(f'~a     (NOT) = {~a}')                       # -11 (two's complement)
print(f'a << 1 (LSH) = {bin(a << 1)} = {a << 1}') # 10100 = 20
print(f'a >> 1 (RSH) = {bin(a >> 1)} = {a >> 1}') # 101 = 5

Operator AND: Pemaskaan Bit

Operator AND (&) menghasilkan 1 hanya ketika kedua bit masukan bernilai 1. Kegunaan utamanya adalah pemaskaan: memilih bit tertentu dari sebuah bilangan sambil mengubah semua bit lainnya menjadi nol. Untuk memeriksa apakah bit k bernilai 1 pada bilangan n, evaluasi n & (1 << k)—jika hasilnya bukan nol, bit k bernilai 1.

AND juga digunakan untuk menghapus bit bernilai 1 terendah: n & (n - 1) menghapus bit 1 paling kanan. Teknik ini digunakan untuk menghitung bit bernilai 1 secara efisien dan memeriksa apakah sebuah bilangan merupakan pangkat dua (pangkat dua memiliki tepat satu bit bernilai 1, sehingga n & (n-1) == 0).

n = 0b10110100  # 180

# Check if bit 5 is set (0-indexed from right)
bit_5 = (n >> 5) & 1
print(f'Bit 5 of {n}: {bit_5}')  # 1

# Clear lowest set bit
print(f'n = {bin(n)}')
print(f'n & (n-1) = {bin(n & (n-1))}')  # 10110000, removed the '100'

# Check power of two
for x in [16, 15, 8, 6, 1, 0]:
    is_pow2 = x > 0 and (x & (x - 1)) == 0
    print(f'{x}: power of 2 = {is_pow2}')

Operator OR: Mengaktifkan Bit

Operator OR (|) menghasilkan 1 jika setidaknya satu bit masukan bernilai 1. Kegunaan utamanya adalah mengaktifkan bit tertentu menjadi 1 tanpa memengaruhi bit lainnya. Untuk mengaktifkan bit k pada bilangan n, gunakan n | (1 << k). Angka 1 yang digeser ke posisi k mengaktifkan bit tersebut; semua bit lainnya tetap tidak berubah karena apa pun yang dikenai OR dengan 0 tetap sama.

OR juga digunakan untuk menggabungkan penanda: jika Anda merepresentasikan penanda fitur sebagai bit individual, Anda dapat mengaktifkan beberapa penanda dengan OR. Sebagai contoh, READ | WRITE | EXECUTE menggabungkan tiga bit izin menjadi satu bilangan bulat.

# Set bit k in n
def set_bit(n, k):
    return n | (1 << k)

n = 0b1000  # 8
print(f'Original: {bin(n)}')
print(f'Set bit 1: {bin(set_bit(n, 1))}')  # 1010
print(f'Set bit 0: {bin(set_bit(n, 0))}')  # 1001

# Flag combination example
READ    = 0b001  # 1
WRITE   = 0b010  # 2
EXECUTE = 0b100  # 4

perms = READ | EXECUTE
print(f'READ|EXECUTE permissions: {bin(perms)} = {perms}')
print(f'Has READ:    {bool(perms & READ)}')
print(f'Has WRITE:   {bool(perms & WRITE)}')
print(f'Has EXECUTE: {bool(perms & EXECUTE)}')

Operator XOR: Membalik dan Mendeteksi Perbedaan

Operator XOR (^) menghasilkan 1 ketika bit masukan berbeda. XOR memiliki tiga sifat aljabar yang kuat: a ^ a = 0 (masukan yang sama saling meniadakan), a ^ 0 = a (nol adalah unsur identitas), dan XOR bersifat komutatif sekaligus asosiatif. Sifat-sifat ini menjadikan XOR alat utama untuk menemukan elemen yang unik.

XOR juga digunakan untuk membalik bit tertentu: n ^ (1 << k) membalik bit k tanpa mengubah bit lainnya. Jika bit k sebelumnya bernilai 0, bit tersebut menjadi 1; jika sebelumnya bernilai 1, bit tersebut menjadi 0.

# XOR properties
print(5 ^ 5)    # 0 — same values cancel
print(5 ^ 0)    # 5 — zero is identity
print(5 ^ 3 ^ 3)  # 5 — 3 cancels itself

# Toggle bit k
def toggle_bit(n, k):
    return n ^ (1 << k)

n = 0b1010
print(f'Toggle bit 3: {bin(toggle_bit(n, 3))}')  # 0010 (was 1)
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}')  # 1011 (was 0)

# XOR swap without temp variable
a, b = 7, 13
a = a ^ b
b = a ^ b   # b now gets original a
a = a ^ b   # a now gets original b
print(f'After XOR swap: a={a}, b={b}')  # a=13, b=7

Operator NOT dan Komplemen Dua

Operator NOT (~) membalik semua bit. Dalam Python, ~n sama dengan -(n+1) karena representasi komplemen dua. Hal ini mengejutkan banyak orang: ~5 = -6, bukan 0b11111010 seperti yang mungkin diperkirakan secara naif. Bilangan bulat Python memiliki presisi tak terbatas, sehingga membalik semua bit bilangan positif menghasilkan nilai negatif dalam komplemen dua.

Dalam praktiknya, Anda jarang menggunakan ~ sendirian dalam Python untuk manipulasi bit. Sebagai gantinya, gunakan operator tersebut bersama AND untuk menghapus bit tertentu, atau hitung ~n & mask ketika nilai pembatas menentukan lebar hingga jumlah bit tertentu (misalnya, & 0xFFFFFFFF untuk 32 bit).

# NOT in Python: ~n = -(n+1)
for n in [0, 1, 5, 127]:
    print(f'~{n} = {~n}')   # all give -(n+1)

# Clear bit k using NOT
def clear_bit(n, k):
    return n & ~(1 << k)

n = 0b1111
print(f'Clear bit 2: {bin(clear_bit(n, 2))}')  # 1011
print(f'Clear bit 0: {bin(clear_bit(n, 0))}')  # 1110

# Limiting to 32-bit with mask
def bitwise_not_32(n):
    return ~n & 0xFFFFFFFF

print(f'32-bit NOT of 5: {bin(bitwise_not_32(5))}')  # 32 zeros then ones

Geser Kiri: Mengalikan dengan Pangkat Dua

Operator geser kiri (<<) menggeser semua bit ke kiri sebanyak k posisi, lalu mengisi posisi kanan yang kosong dengan nol. Operasi ini setara dengan mengalikan dengan 2^k. Menggeser ke kiri sebanyak 1 posisi menggandakan nilai; menggeser ke kiri sebanyak k posisi mengalikan nilai dengan 2^k.

Dalam masalah wawancara, geser kiri paling sering digunakan untuk membuat mask bit: 1 << k menghasilkan bilangan yang hanya memiliki bit k bernilai 1. Inilah dasar semua operasi manipulasi bit—mengaktifkan, menghapus, membalik, dan memeriksa bit individual semuanya dimulai dengan 1 << k.

# Left shift = multiply by 2^k
n = 1
for k in range(8):
    print(f'1 << {k} = {1 << k}')   # 1,2,4,8,16,32,64,128

# Practical use: creating bitmasks
def bit_mask(k):
    return 1 << k

print(f'\nBitmask for bit 0: {bin(bit_mask(0))}')  # 1
print(f'Bitmask for bit 3: {bin(bit_mask(3))}')  # 1000
print(f'Bitmask for bit 7: {bin(bit_mask(7))}')  # 10000000

# Fast exponentiation: 2^10 = 1024
print(f'2^10 = {1 << 10}')  # 1024

Geser Kanan: Membagi dengan Pangkat Dua

Operator geser kanan (>>) menggeser semua bit ke kanan sebanyak k posisi dan membuang k bit paling kanan. Operasi ini setara dengan pembagian bilangan bulat dengan 2^k. Geser kanan Python selalu bersifat aritmetis: bit paling kiri diisi dengan bit tanda (0 untuk bilangan positif, 1 untuk bilangan negatif).

Trik wawancara yang umum: untuk mengambil bit k dari bilangan n, gunakan (n >> k) & 1. Operasi ini menggeser bit k ke posisi 0 dan meniadakan semua bit lainnya. Ini adalah cara paling bersih untuk memeriksa bit tertentu tanpa perlu menghitung dan membandingkan mask penuh.

# Right shift = integer division by 2^k
n = 64
for k in range(7):
    print(f'{n} >> {k} = {n >> k}')   # 64,32,16,8,4,2,1

# Extract bit k from n
def get_bit(n, k):
    return (n >> k) & 1

n = 0b10110101  # 181
print(f'\nBits of {n} ({bin(n)}):')
for k in range(8):
    print(f'  Bit {k}: {get_bit(n, k)}')

# Negative number right shift (arithmetic)
print(f'-8 >> 1 = {-8 >> 1}')   # -4 (fills with sign bit 1)

Ringkasan Trik Bit Praktis

Berikut adalah kumpulan ungkapan manipulasi bit yang paling umum dan akan Anda temui dalam wawancara. Hafalkan pola-pola ini—pola tersebut berulang kali muncul dalam puluhan masalah:

  • n & 1 — memeriksa apakah n ganjil
  • n & (n-1) — menghapus bit bernilai 1 terendah
  • n & -n — mengisolasi bit bernilai 1 terendah
  • n | (1 << k) — mengaktifkan bit k
  • n & ~(1 << k) — menghapus bit k
  • n ^ (1 << k) — membalik bit k
  • (n >> k) & 1 — memeriksa bit k
# Bit trick cheatsheet — all at once
n = 0b10110100  # 180

print(f'n = {bin(n)} = {n}')
print(f'n & 1       (odd check)         = {n & 1}')          # 0: even
print(f'n & (n-1)   (clear lowest bit)  = {bin(n & (n-1))}')
print(f'n & -n      (isolate lowest bit) = {bin(n & -n)}')
print(f'n | (1<<1)  (set bit 1)          = {bin(n | (1<<1))}')
print(f'n & ~(1<<2) (clear bit 2)        = {bin(n & ~(1<<2))}')
print(f'n ^ (1<<5)  (toggle bit 5)       = {bin(n ^ (1<<5))}')
print(f'(n>>4) & 1  (check bit 4)        = {(n>>4) & 1}')

Menghitung Bit Bernilai 1

Menghitung jumlah bit 1 dalam bilangan bulat disebut penghitungan populasi (jumlah bit bernilai 1). Pendekatan sederhana mengiterasi semua bit. Trik Brian Kernighan lebih cepat: hapus berulang kali bit bernilai 1 terendah dengan n &= n - 1, lalu hitung jumlah iterasi hingga n menjadi 0. Setiap iterasi menghapus tepat satu bit 1, sehingga perulangan berjalan tepat sebanyak jumlah bit 1.

Python 3.10+ menyediakan int.bit_count() yang langsung mengembalikan jumlahnya. Untuk versi yang lebih lama, trik Kernighan adalah pendekatan manual standar. Teknik ini juga menyelesaikan masalah 'Bobot Hamming' di LeetCode.

# Method 1: naive O(log n)
def count_bits_naive(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Method 2: Brian Kernighan O(k) where k = number of set bits
def count_bits_fast(n):
    count = 0
    while n:
        n &= n - 1   # clear lowest set bit
        count += 1
    return count

# Method 3: Python built-in (3.10+)
# n.bit_count()

for x in [0, 1, 7, 255, 180, 1024]:
    naive = count_bits_naive(x)
    fast  = count_bits_fast(x)
    print(f'{x:4d} ({bin(x):10s}): naive={naive}, fast={fast}')

Manipulasi Bit dalam Python: Hal Penting yang Perlu Diperhatikan

Tidak seperti C/Java, bilangan bulat Python dapat berukuran sebesar apa pun—tidak ada luapan 32 bit atau 64 bit. Artinya, Anda harus membatasi hasil secara manual ke lebar tetap ketika menyelesaikan masalah yang mengharapkan perilaku 32 bit: gunakan & 0xFFFFFFFF untuk mempertahankan hanya 32 bit rendah.

Operator NOT ~n dalam Python mengembalikan -(n+1), bukan versi dengan bit yang dibalik seperti yang mungkin Anda harapkan dari C. Untuk masalah 32 bit, gunakan ~n & 0xFFFFFFFF atau hitung 0xFFFFFFFF ^ n untuk mendapatkan komplemen 32 bit yang diharapkan. Perbedaan ini sering membingungkan kandidat yang terbiasa dengan manipulasi bit gaya C.

# Python vs C gotchas
# In C: unsigned 32-bit NOT of 5 = 4294967290
# In Python: ~5 = -6
print(f'Python ~5 = {~5}')              # -6
print(f'32-bit ~5 = {~5 & 0xFFFFFFFF}') # 4294967290

# No integer overflow in Python
big = 1 << 100   # 2^100: huge number, no overflow
print(f'2^100 = {big}')  # works fine

# Right shift on negatives: arithmetic (sign-extending)
print(f'-1 >> 3 = {-1 >> 3}')   # -1 (all ones shifted in)

# Safe 32-bit mask for problems expecting C/Java semantics
MASK32 = 0xFFFFFFFF
result = (5 + 0xFFFFFFFE) & MASK32  # simulates 32-bit overflow
print(f'5 + (-2) in 32-bit = {result}')  # 3

Operator Geser dan Perkalian

Geser kiri dan geser kanan menyediakan cara yang sangat cepat untuk mengalikan atau membagi dengan pangkat dua. Pada perangkat keras, operasi geser bit merupakan operasi satu instruksi, sedangkan perkalian dan pembagian membutuhkan banyak siklus. Dalam Python, perkalian bilangan bulat sudah efisien, tetapi memahami hubungan ini membantu Anda melihat pola bit dengan lebih jelas.

Identitas yang berguna: untuk memeriksa apakah n merupakan kelipatan 2^k, gunakan (n & (2^k - 1)) == 0. Mask 2^k - 1 memiliki semua k bit terendah bernilai 1; melakukan AND dengannya menghasilkan sisa ketika dibagi dengan 2^k. Operasi ini setara dengan n % (2^k), tetapi lebih cepat dalam bahasa berbasis C.

# Shift vs arithmetic equivalence
for k in range(1, 5):
    n = 48
    print(f'{n} * 2^{k} = {n * (2**k)} = {n << k} (left shift)')
    print(f'{n} // 2^{k} = {n // (2**k)} = {n >> k} (right shift)')
    print()

# Check divisibility by power of 2
def divisible_by_power_of_2(n, k):
    mask = (1 << k) - 1   # 2^k - 1: lower k bits all 1
    return (n & mask) == 0

for n in [16, 24, 32, 15, 100]:
    print(f'{n} divisible by 4? {divisible_by_power_of_2(n, 2)}')

Pemeriksaan Singkat

Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.

Ringkasan Pelajaran

Dalam pelajaran ini Anda mempelajari bahwa: AND menerapkan mask pada bit, OR mengaktifkan bit, XOR membalik bit dan mendeteksi perbedaan, NOT membalik bit (menghasilkan -(n+1) dalam Python), dan operasi geser mengalikan atau membagi dengan pangkat dua, n & (n-1) menghapus bit bernilai 1 terendah dan menjadi dasar pemeriksaan pangkat dua serta penghitungan bit, serta Python tidak memiliki luapan dengan lebar tetap, sehingga masalah 32 bit memerlukan pemaskaan eksplisit menggunakan & 0xFFFFFFFF. Berikutnya, kita akan mengeksplorasi sifat inversi dirinya sendiri pada XOR untuk menyelesaikan kelompok masalah bilangan tunggal.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Operator Bitwise: AND, OR, XOR, NOT, Pergeseran” gratis?

Ya — teks lengkap “Operator Bitwise: AND, OR, XOR, NOT, Pergeseran” 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 “Operator Bitwise: AND, OR, XOR, NOT, Pergeseran”?

Tinjau keenam operator bitwise dengan tabel kebenaran dan contoh Python, lalu pahami hubungan pergeseran kiri/kanan dengan perkalian dan pembagian dua 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 1 dari 4.

Berapa lama pelajaran “Operator Bitwise: AND, OR, XOR, NOT, Pergeseran” 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

  1. Operator Bitwise: AND, OR, XOR, NOT, Pergeseran
  2. Single Number dan Sifat XOR
  3. Masker Bit: Set, Clear, Toggle, Check
  4. Menghitung Bit, Angka yang Hilang, dan Membalik Bit
← Kembali ke Coding Interview Prep