Belajar Algoritm - Bit Manipulation Tricks

#Pendahuluan

Setelah di episode 11 kita membahas Backtracking, pada episode ini kita menutup FASE 3: SEARCHING & DIVIDE & CONQUER dengan bit manipulation — teknik yang beroperasi langsung pada representasi biner angka. Bit manipulation bukan hanya trik untuk competitive programming; ia adalah fondasi untuk memahami bagaimana komputer benar-benar bekerja dan mengapa operasi tertentu bisa dilakukan dalam satu langkah.

Menguasai bit manipulation memberikan keunggulan dalam optimasi — operasi bitwise seperti AND, OR, XOR, dan shift bisa menggantikan operasi yang lebih mahal secara komputasi. Di era AI apps, bit manipulation juga relevan untuk manipulasi bitmap, mask operations, dan efficient set operations.

#Operator Bitwise Dasar

#Trik Bitwise yang Sering Dipakai

#Cek Ganjil/Genap

def is_odd(n):
    return n & 1  # bit terakhir = 1 → ganjil

Lebih cepat dari n % 2 karena menghindari operasi modulo.

#Toggle Bit ke-N

def toggle_bit(n, pos):
    return n ^ (1 << pos)

XOR dengan 1 di posisi tertentu akan mengubah bit di posisi itu tanpa mempengaruhi yang lain.

#Isolasi Rightmost 1

def isolate_rightmost_1(n):
    return n & (-n)

-n dalam two's complement adalah ~n + 1. n & (-n) menghasilkan hanya bit paling kanan yang bernilai 1.

#Hapus Rightmost 1

def remove_rightmost_1(n):
    return n & (n - 1)

Operasi ini menghapus satu bit 1 setiap kali dipanggil — berguna untuk menghitung jumlah bit 1 (popcount).

#Cek Apakah Power of 2

def is_power_of_2(n):
    return n > 0 and (n & (n - 1)) == 0

Power of 2 hanya punya satu bit 1 → n & (n-1) menghapusnya → hasilnya 0.

#Bitmasking untuk Subset Enumeration

Bitmask memungkinkan kita merepresentasikan subset dari set sebagai angka. Setiap bit merepresentasikan keberadaan sebuah elemen:

def enumerate_subsets(items):
    n = len(items)
    result = []
    # 2^n subset: dari 000...0 sampai 111...1
    for mask in range(1 << n):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(items[i])
        result.append(subset)
    return result
 
# enumerate_subsets(['A','B','C']) → 8 subset

Kompleksitas: O(2^n × n) — efektif untuk n ≤ 20 (≈ 20 juta operasi).

#XOR Magic: Single Number

XOR memiliki properti unik: a ^ a = 0 dan a ^ 0 = a. Ini berarti XOR dari semua elemen kecuali satu yang muncul sekali akan menghasilkan elemen tersebut.

def single_number(nums):
    """Satu elemen muncul sekali, yang lain dua kali"""
    result = 0
    for num in nums:
        result ^= num
    return result

Time: O(n), Space: O(1) — tanpa hash map atau sorting.

#Bit Manipulation dalam Competitive Programming

#Penutup

Pada episode 12 ini, kalian telah memahami:

• Operator bitwise: AND, OR, XOR, NOT, shift — operasi dasar yang sangat cepat.
• Trik: cek ganjil/genap, toggle, isolasi rightmost 1, hapus rightmost 1, cek power of 2.
• Bitmasking: subset enumeration dalam O(2^n × n).
• XOR magic: single number detection tanpa memori tambahan.

Ini menutup FASE 3: SEARCHING & DIVIDE & CONQUER. Di episode 13 selanjutnya kita masuk ke FASE 4: GREEDY & DYNAMIC PROGRAMMING — membahas Greedy Algorithms: prinsip greedy choice property, optimal substructure, dan masalah klasik seperti activity selection, Huffman coding, dan fractional knapsack. Sampai jumpa di episode 13!