အခန်း ၂၄ - Bit Manipulation

အရင်အခန်းတွေမှာ data ကို array, hash table, tree စတဲ့ structure တွေနဲ့ ကိုင်တွယ်ခဲ့ပါတယ်။ ဒါပေမယ့် computer ထဲမှာ ဒီ data အကုန်လုံးဟာ နောက်ဆုံးမှာ bit (0 နဲ့ 1) တွေ အဖြစ်သာ ရှိနေတာပါ။ Bit Manipulation ဆိုတာ — အဲ့ဒီ bit တွေကို တိုက်ရိုက် ကိုင်တွယ်တဲ့ နည်းပညာပါ။

Bit manipulation ကို နေ့စဉ် app development မှာ အမြဲ မသုံးပေမယ့် — permission / role flags, feature flag, compact settings, low-level optimization စတဲ့ နေရာတွေမှာ အလွန် အသုံးဝင်တယ်။ ဥပမာ — user တစ်ယောက်ရဲ့ permission ၈ မျိုးကို — boolean ၈ ခု အစား — integer တစ်ခုတည်းနဲ့ သိမ်းလို့ ရတယ် (bit ၈ လုံး)။ ဒီအခန်းမှာ — binary အခြေခံ၊ bitwise operator တွေ၊ bit mask လုပ်ဆောင်ချက်တွေ၊ ပြီးတော့ classic ပြဿနာ ၅ ခု ဖြေသွားပါမယ်။

Binary အခြေခံ

Computer က ဂဏန်းတွေကို binary (base-2) — 0 နဲ့ 1 တွေနဲ့ ကိုယ်စားပြုတယ်။ position တစ်ခုစီက 2 ရဲ့ ထပ်ကိန်း တန်ဖိုး —

   ဒဿမ (decimal) 13  →  binary 1101
        1      1      0      1
        ×8     ×4     ×2     ×1      ← 2³ 2² 2¹ 2⁰
        8  +   4  +   0  +   1   =  13

bit တစ်လုံးစီကို position (index) နဲ့ ရည်ညွှန်းတယ် — အညာဆုံး (least significant) က position 0။ ဥပမာ 1101 မှာ — position 0, 2, 3 က 1၊ position 1 က 0။

Bitwise Operators

bit တွေကို ကိုင်တွယ်တဲ့ အခြေခံ operator ၆ ခု —

AND (&), OR (|), XOR (^)

bit ၂ လုံးကို position အလိုက် နှိုင်းတာ —

   a = 5 = 0101
   b = 3 = 0011

   a & b  (AND — ၂ ခုလုံး 1 မှ 1):   0001 = 1
   a | b  (OR  — တစ်ခုခု 1 ဆို 1):    0111 = 7
   a ^ b  (XOR — မတူမှ 1):            0110 = 6

• AND (&) — bit ၂ လုံးစလုံး 1 မှ 1။ "bit စစ်ထုတ် (mask)" ဖို့ သုံး။
• OR (|) — တစ်ခုခု 1 ဆို 1။ "bit ဖွင့် (set)" ဖို့ သုံး။
• XOR (^) — မတူမှ 1 (တူရင် 0)။ ဂုဏ်သတ္တိ အရေးကြီး ၂ ခု — a ^ a = 0 (ကိုယ့်ကိုယ်ကို XOR = 0)၊ a ^ 0 = a။ ဒါက "single number" လို ပြဿနာတွေရဲ့ သော့ချက်ပါ။

NOT (~)

bit အကုန်လုံးကို ပြောင်းပြန်လှန် (0↔1)။ signed integer မှာ — sign bit ပါ ပြောင်းလို့ ရလဒ်က နုတ်ကိန်း ဖြစ်တယ် (two's complement)။

   ~5  →  ...11111010  =  -6   (two's complement: ~x = -x - 1)

Left Shift (<<), Right Shift (>>)

bit တွေကို ဘယ်/ညာ ရွှေ့တာ —

   5 << 1  →  0101 → 1010 = 10   (ဘယ်ရွှေ့ ၁ = × 2)
   5 << 2  →  0101 → 10100 = 20  (ဘယ်ရွှေ့ 2 = × 4)
   5 >> 1  →  0101 → 0010 = 2    (ညာရွှေ့ ၁ = ÷ 2, အကြွင်း ပစ်)

• Left shift n << k = n × 2^k။ 1 << k က — position k မှာ bit တစ်လုံးတည်း 1 ဖြစ်တဲ့ ဂဏန်း ($2^k$) — bit mask ဆောက်ဖို့ အရေးကြီး။
• Right shift n >> k = n ÷ 2^k။

Bit Mask — Bit တစ်လုံးချင်း ကိုင်တွယ်ခြင်း

ဂဏန်းတစ်ခုရဲ့ position i က bit ကို — 1 << i ဆိုတဲ့ "mask" နဲ့ ပေါင်းပြီး ကိုင်တွယ်တယ်။ အခြေခံ လုပ်ဆောင်ချက် ၄ ခု —

   mask = 1 << i      (position i မှာ bit တစ်လုံး 1)

   Check  (bit ဖွင့်ထား/မထား):   (n >> i) & 1      → 1 ဆို ဖွင့်ထား
   Set    (bit ဖွင့်):            n | (1 << i)      → position i ကို 1
   Clear  (bit ပိတ်):            n & ~(1 << i)     → position i ကို 0
   Toggle (ပြောင်းပြန်):          n ^ (1 << i)      → 0↔1 လှန်

   n = 1010 (=10),  i = 0:
     Check:  (1010 >> 0) & 1 = 0   → position 0 ပိတ်ထား
     Set:    1010 | 0001 = 1011    → position 0 ဖွင့် (=11)
   n = 1010,  i = 1:
     Clear:  1010 & ~0010 = 1000   → position 1 ပိတ် (=8)
     Toggle: 1010 ^ 0010 = 1000    → position 1 လှန် (=8)

Permission Flags — အသုံးအများဆုံး Real-world Pattern

bit manipulation ရဲ့ အသုံးအဝင်ဆုံး real-world pattern က permission / feature flag ပါ။ permission တစ်ခုစီကို bit တစ်လုံး အဖြစ် သတ်မှတ်ပြီး — integer တစ်ခုတည်းနဲ့ permission အများကြီး သိမ်းတယ်။

   READ  = 1 = 001       (bit 0)
   WRITE = 2 = 010       (bit 1)
   EXEC  = 4 = 100       (bit 2)

   user permission = READ | WRITE = 001 | 010 = 011 (=3)

   "WRITE ရှိလား?"    permission & WRITE  != 0  →  ရှိ ✓
   "EXEC ထည့်":       permission | EXEC         →  111 (=7)
   "READ ဖြုတ်":      permission & ~READ        →  010 (=2)

ဒီနည်းက — boolean field အများကြီး အစား integer (int = bit 32 လုံး) တစ်ခုနဲ့ flag ၃၂ မျိုး သိမ်းနိုင်လို့ — database column, network packet, config setting တွေမှာ နေရာ အလွန် သက်သာတယ် (Linux file permission chmod 755 ဟာ ဒီ pattern ပါ)။

Real-world Examples

• Role / Permission System — user role ကို READ|WRITE|DELETE... bit flag integer တစ်ခုနဲ့ သိမ်း၊ permission စစ်တာ & တစ်ချက်နဲ့ ($O(1)$)။
• Feature Flags — app ရဲ့ feature ၃၂ မျိုးကို integer တစ်ခုနဲ့ on/off — A/B testing, gradual rollout။
• Compact Settings — IoT device, game state, network protocol မှာ — setting အများကြီးကို byte နည်းနည်းနဲ့ pack လုပ်တာ (bandwidth/memory ချွေတာ)။
• Low-level Optimization — × 2 အစား << 1၊ % 2 အစား & 1၊ hash function, graphics, cryptography မှာ bit trick။
• Bitset / Bloom Filter — element ရှိမရှိ စစ်ဖို့ bit array သုံးတာ (database, cache)။

Questions

Bit manipulation ပြဿနာ ဖြေတဲ့အခါ — ဂဏန်းကို binary အဖြစ် မြင်ပြီး — XOR ဂုဏ်သတ္တိ (a^a=0)၊ n & (n-1) (အညာဆုံး bit ဖျက်)၊ 1 << i (mask) စတဲ့ trick တွေ သုံးတာပါ။ classic ၅ ခု ဖြေကြည့်ရအောင်။

၁။ Single Number

integer array nums — element တိုင်း ၂ ခါစီ ပါ၊ တစ်ခုတည်းသာ ၁ ခါ ပါတယ်။ အဲ့ဒီ တစ်ခါပဲ ပါတဲ့ element ကို ရှာပါ။ (extra memory မသုံးဘဲ $O(n)$)။

Input: nums = [4,1,2,1,2]
Output: 4

ရှင်းလင်းချက်

XOR ဂုဏ်သတ္တိ: a ^ a = 0 နဲ့ a ^ 0 = a။ array အကုန်ကို XOR ပေါင်းလိုက်ရင် — ၂ ခါစီ ပါတဲ့ element တွေ အချင်းချင်း ဖျက်ပြီး (x ^ x = 0) — တစ်ခါပဲ ပါတာ ကျန်တယ်။ hash table မလို၊ space $O(1)$။

nums = [4,1,2,1,2] ကို XOR —

   0 ^ 4 = 4
   4 ^ 1 = 5
   5 ^ 2 = 7
   7 ^ 1 = 6
   6 ^ 2 = 4      ← 1,1 ဖျက်၊ 2,2 ဖျက် → 4 ကျန် ✓

Time Complexity: $O(n)$ - တစ်ခေါက်ပဲ ဖြတ်။
Space Complexity: $O(1)$ - variable တစ်ခုပဲ။

Java Solution

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int x : nums) single ^= x;        // ၂ ခါ ပါတာ အချင်းချင်း ဖျက်
        return single;                         // တစ်ခါပဲ ပါတာ ကျန်
    }
}

၂။ Number of 1 Bits (Count Set Bits)

integer တစ်ခု ပေးထားသည်။ သူ့ binary မှာ 1 bit ဘယ်နှ လုံး ရှိလဲ ပြန်ပါ (Hamming weight)။

Input: n = 11  (binary 1011)
Output: 3
   (bit position 0, 1, 3 — '1' ၃ လုံး)

ရှင်းလင်းချက်

n & (n - 1) trick: ဒီ operation က — အညာဆုံး 1 bit ကို 0 ပြောင်းပစ်တယ်။ ဒါကြောင့် — n က 0 မဖြစ်မချင်း ဒီ operation ထပ်လုပ်ပြီး၊ ဘယ်နှ ခါ လုပ်ရလဲ ရေတွက်ရင် — 1 bit အရေအတွက် ရတယ်။ bit အကုန် (၃၂ လုံး) loop မလိုဘဲ — 1 bit အရေအတွက် အတိုင်းပဲ loop လုပ်လို့ ပိုမြန်တယ်။

n = 11 (1011) ကို လိုက်ကြည့်ရအောင် —

   n = 1011,  n-1 = 1010  →  n & (n-1) = 1010  (count=1)
   n = 1010,  n-1 = 1001  →  n & (n-1) = 1000  (count=2)
   n = 1000,  n-1 = 0111  →  n & (n-1) = 0000  (count=3)
   n = 0  →  ရပ်။  '1' bit = 3 ✓

Time Complexity: $O(k)$ - k = 1 bit အရေအတွက် (≤ 32)။
Space Complexity: $O(1)$။

Java Solution

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);                      // အညာဆုံး '1' bit ဖျက်
            count++;
        }
        return count;
    }
}

၃။ Power of Two

integer n ပေးထားသည်။ n က ၂ ရဲ့ ထပ်ကိန်း (1, 2, 4, 8, ...) ဖြစ်/မဖြစ် ပြန်ပါ။

Input: n = 16
Output: true   (16 = 2⁴)

Input: n = 6
Output: false  (6 = 2 × 3)

ရှင်းလင်းချက်

အဓိက အသိ: ၂ ရဲ့ ထပ်ကိန်းတွေက binary မှာ 1 bit တစ်လုံးတည်း ရှိတယ် (1=0001, 2=0010, 4=0100, 8=1000)။ ဒါကြောင့် — n & (n-1) == 0 (အညာဆုံး 1 bit ဖျက်လိုက်ရင် 0 ကျန်) ဆို — 1 bit တစ်လုံးတည်း ရှိ = power of two။ (n > 0 ပါ စစ်ရတယ် — 0 နဲ့ နုတ်ကိန်း မပါအောင်)။

   16 = 10000,  15 = 01111  →  16 & 15 = 00000 = 0  → true ✓
   6  = 00110,   5 = 00101  →   6 &  5 = 00100 ≠ 0  → false

Time Complexity: $O(1)$ - operation ၂ ချက်ပဲ။
Space Complexity: $O(1)$။

Java Solution

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;    // '1' bit တစ်လုံးတည်း
    }
}

၄။ Missing Number

0 ကနေ n ထိ ဂဏန်း n ခု ထဲက — တစ်ခု ပျောက်နေတဲ့ array nums (အရှည် n) ပေးထားသည်။ ပျောက်နေတဲ့ ဂဏန်း ပြန်ပါ။

Input: nums = [3,0,1]
Output: 2
   (0,1,2,3 ထဲက 2 ပျောက်)

ရှင်းလင်းချက်

XOR trick: index အကုန် (0..n) နဲ့ nums value အကုန်ကို XOR ပေါင်းလိုက်ရင် — ရှိတဲ့ ဂဏန်းတွေ အချင်းချင်း ဖျက် (value နဲ့ index တူတာ ဖျက်) ပြီး — ပျောက်နေတဲ့ ဂဏန်း ကျန်တယ်။ (a^a=0 ဂုဏ်သတ္တိ — Single Number နဲ့ တူ)။ Sum နည်း (n(n+1)/2 - sum) နဲ့လည်း ရပေမယ့် — XOR က overflow မဖြစ်လို့ ပိုလုံခြုံ။

nums = [3,0,1], n = 3 —

   res = 3 (=n)
   i=0:  res ^ 0 ^ nums[0]=3  →  3 ^ 0 ^ 3 = 0
   i=1:  res ^ 1 ^ nums[1]=0  →  0 ^ 1 ^ 0 = 1
   i=2:  res ^ 2 ^ nums[2]=1  →  1 ^ 2 ^ 1 = 2   → 2 ✓

Time Complexity: $O(n)$။
Space Complexity: $O(1)$။

Java Solution

class Solution {
    public int missingNumber(int[] nums) {
        int res = nums.length;                 // n နဲ့ စ (index 0..n-1 အပြင် n ပါ)
        for (int i = 0; i < nums.length; i++) {
            res ^= i ^ nums[i];                // index နဲ့ value ၂ ခုလုံး XOR
        }
        return res;                            // ဖျက်လို့ မရတဲ့ (ပျောက်) ဂဏန်း ကျန်
    }
}

၅။ Subsets (using Bits)

ထပ်တူ မပါတဲ့ integer array nums (အရှည် n) ပေးထားသည်။ ဖြစ်နိုင်တဲ့ subset အကုန်လုံး (power set) ကို ပြန်ပါ။

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
   (subset 2³ = 8 ခု)

ရှင်းလင်းချက်

element n ခုရဲ့ subset က $2^n$ ခု ရှိ — element တစ်ခုစီအတွက် "ပါ (1) / မပါ (0)" ၂ ရွေး။ ဒါက bit ပုံစံနဲ့ တိုက်ဆိုင်တယ်! 0 ကနေ 2^n - 1 ထိ ဂဏန်း တစ်ခုစီကို — bitmask အဖြစ် ကြည့်ရင် — bit i က 1 ဆို nums[i] ပါ၊ 0 ဆို မပါ — subset တစ်ခုစီ ရတယ်။

nums = [1,2,3] — mask 0..7 —

   mask  binary   subset
   0     000      []
   1     001      [1]            (bit 0 ဖွင့်)
   2     010      [2]
   3     011      [1,2]
   4     100      [3]
   5     101      [1,3]
   6     110      [2,3]
   7     111      [1,2,3]

Time Complexity: $O(n \times 2^n)$ - subset $2^n$ ခု × element n စစ်။
Space Complexity: $O(n \times 2^n)$ - output (extra $O(1)$)။

Java Solution

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {   // 0 .. 2^n - 1
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) subset.add(nums[i]);  // bit i ဖွင့် → ပါ
            }
            result.add(subset);
        }
        return result;
    }
}