位元運算 — AND、OR、XOR 六大運算子與 Bitmask 技巧 | 資料結構與演算法

// ━━ Lowbit：取出 x 最低位的 1 ━━
// x & (-x) = x & (~x + 1)（二補數定義）
function lowbit(x: number): number {
  return x & (-x);
}
// lowbit(12) = lowbit(0b1100) = 0b0100 = 4
// lowbit(6)  = lowbit(0b0110) = 0b0010 = 2
// lowbit(8)  = lowbit(0b1000) = 0b1000 = 8

// ━━ Brian Kernighan 算法：計算二進位中 1 的個數 ━━
// 時間 O(popcount(n))，比逐位掃描的 O(32) 更快
function popcount(n: number): number {
  let count = 0;
  while (n > 0) {
    n &= n - 1; // 每次清除最低位的 1
    count++;
  }
  return count;
}
// popcount(106) = popcount(0b01101010)
// 0b01101010 → 0b01101000 → 0b01100000 → 0b01000000 → 0b00000000
// 共 4 次 → count = 4

// ━━ 查表法 popcount（O(1) — 實際競程常用） ━━
const popcount256: number[] = new Array(256).fill(0);
for (let i = 1; i < 256; i++) {
  popcount256[i] = popcount256[i >> 1] + (i & 1);
}

function popcountFast(n: number): number {
  // 32 位整數分 4 個 byte 分別查表
  return popcount256[n & 0xFF] +
         popcount256[(n >> 8) & 0xFF] +
         popcount256[(n >> 16) & 0xFF] +
         popcount256[(n >> 24) & 0xFF];
}

// ━━ LeetCode 191：Number of 1 Bits ━━
function hammingWeight(n: number): number {
  let count = 0;
  while (n !== 0) {
    n &= n - 1; // Brian Kernighan
    count++;
  }
  return count;
}

// ━━ LeetCode 338：Counting Bits — O(n) DP ━━
// dp[i] = i 的 popcount，利用 i >> 1 已知的子問題遞推
function countBits(n: number): number[] {
  const dp = new Array<number>(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    // i >> 1 去掉最低位；i & 1 最低位的貢獻
    dp[i] = dp[i >> 1] + (i & 1);
  }
  return dp;
}
// countBits(5) → [0, 1, 1, 2, 1, 2]

// 另一種遞推（利用 x & (x-1) 清除最低位）
function countBitsV2(n: number): number[] {
  const dp = new Array<number>(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    dp[i] = dp[i & (i - 1)] + 1; // dp[i 去掉最低位的1] + 1
  }
  return dp;
}

// ━━ 列舉 n 個元素的所有 2ⁿ 個子集 ━━
function enumerateSubsets(elements: number[]): void {
  const n = elements.length;
  const total = 1 << n; // 2^n 個子集

  for (let mask = 0; mask < total; mask++) {
    const subset: number[] = [];
    for (let i = 0; i < n; i++) {
      if ((mask >> i) & 1) { // 第 i 位是否為 1
        subset.push(elements[i]);
      }
    }
    console.log(`mask=${mask.toString(2).padStart(n, '0')}: [${subset}]`);
  }
}

// enumerateSubsets([1, 2, 3])：
// mask=000: []        mask=001: [1]     mask=010: [2]
// mask=011: [1,2]     mask=100: [3]     mask=101: [1,3]
// mask=110: [2,3]     mask=111: [1,2,3]

// ━━ 列舉 mask 的所有子集（子集 DP 關鍵操作） ━━
// 技巧：sub = (sub - 1) & mask，每次去掉 sub 中最低位的 1
// 時間：對所有 mask 枚舉子集，總計 O(3ⁿ)（三進位分析）
function enumerateSubsetsOfMask(mask: number): number[] {
  const subsets: number[] = [];
  for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
    subsets.push(sub);
    // 注意：sub = 0 時 (sub - 1) & mask = (-1) & mask = mask，會無限循環
    // 所以用 sub > 0 作終止條件，最後手動加入空集
  }
  subsets.push(0); // 加入空集 {}
  return subsets;
}
// mask = 0b110 → [6(110), 4(100), 2(010), 0(000)]

// ━━ LeetCode 78：Subsets（Bitmask 列舉法） ━━
function subsets(nums: number[]): number[][] {
  const n = nums.length;
  const result: number[][] = [];

  for (let mask = 0; mask < (1 << n); mask++) {
    const subset: number[] = [];
    for (let i = 0; i < n; i++) {
      if ((mask >> i) & 1) {
        subset.push(nums[i]);
      }
    }
    result.push(subset);
  }

  return result;
}
// subsets([1,2,3]) → [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
// 順序對應 mask 的二進位：000, 001, 010, 011, 100, 101, 110, 111

console.log(subsets([1, 2, 3]));
// 輸出：[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

// ━━ LeetCode 136：Single Number — 找唯一不重複的數 ━━
// 思路：所有出現兩次的數 XOR 後為 0，最終結果就是唯一的數
function singleNumber(nums: number[]): number {
  return nums.reduce((xor, n) => xor ^ n, 0);
}
// [4,1,2,1,2] → 0^4^1^2^1^2 = (1^1)^(2^2)^4 = 0^0^4 = 4
console.log(singleNumber([4, 1, 2, 1, 2])); // 輸出：4
console.log(singleNumber([2, 2, 1]));        // 輸出：1

// ━━ LeetCode 268：Missing Number — 找 [0, n] 中缺失的數 ━━
// 思路：將 [0, n] 與陣列全部 XOR，重複的數消除，剩下的就是缺失的數
function missingNumber(nums: number[]): number {
  let xor = nums.length; // 從 n 開始（[0, n] 包含 n）
  for (let i = 0; i < nums.length; i++) {
    xor ^= i ^ nums[i]; // i 和 nums[i] 分別 XOR
  }
  return xor;
}
// [3,0,1] → xor = 3 ^ (0^3) ^ (1^0) ^ (2^1) = 2
console.log(missingNumber([3, 0, 1])); // 輸出：2
console.log(missingNumber([9,6,4,2,3,5,7,0,1])); // 輸出：8

// ━━ LeetCode 371：Sum of Two Integers（不用 + 運算子）━━
// 思路：XOR 計算不進位的和，AND 左移計算進位，重複直到無進位
function getSum(a: number, b: number): number {
  while (b !== 0) {
    const carry = (a & b) << 1; // 進位（每個有進位的位元左移一位）
    a = a ^ b;                   // 不帶進位的和
    b = carry;
  }
  return a;
}
// getSum(3, 5)：
// iter1: carry=(011 & 101)<<1 = 010, a = 011^101 = 110, b = 010
// iter2: carry=(110 & 010)<<1 = 100, a = 110^010 = 100, b = 100
// iter3: carry=(100 & 100)<<1 =1000, a = 100^100 = 000, b =1000
// iter4: carry=(000 &1000)<<1 =   0, a = 000^1000= 1000, b = 0 → return 8
console.log(getSum(3, 5));   // 輸出：8
console.log(getSum(-3, -5)); // 輸出：-8

// ━━ 判斷是否為 2 的冪（LeetCode 231）━━
// 2 的冪的二進位表示只有一個位元為 1
// 例：8 = 1000，8-1 = 0111，8 & 7 = 0000
function isPowerOfTwo(n: number): boolean {
  return n > 0 && (n & (n - 1)) === 0;
}
console.log(isPowerOfTwo(16)); // 輸出：true  (10000 & 01111 = 00000)
console.log(isPowerOfTwo(18)); // 輸出：false (10010 & 10001 ≠ 0)

// ━━ XOR Swap（不用暫存變數交換兩數）━━
function xorSwap(arr: number[], i: number, j: number): void {
  if (i === j) return; // 重要！相同位置 XOR 會清零
  arr[i] ^= arr[j];
  arr[j] ^= arr[i]; // arr[j] = arr[j] ^ (原 arr[i] ^ arr[j]) = 原 arr[i]
  arr[i] ^= arr[j]; // arr[i] = (原 arr[i] ^ arr[j]) ^ 原 arr[i] = 原 arr[j]
}

// 使用 Bitmask 管理功能開關，支援組合查詢
const Features = {
  DARK_MODE:     1 << 0,  // 0000 0001
  NOTIFICATIONS: 1 << 1,  // 0000 0010
  ANALYTICS:     1 << 2,  // 0000 0100
  BETA_FEATURES: 1 << 3,  // 0000 1000
  PREMIUM:       1 << 4,  // 0001 0000
  AI_ASSISTANT:  1 << 5,  // 0010 0000
} as const;

type FeatureFlag = typeof Features[keyof typeof Features];

class FeatureFlagService {
  private userFlags: Map<string, number> = new Map();

  // 啟用功能：OR 置位
  enableFeature(userId: string, feature: FeatureFlag): void {
    const current = this.userFlags.get(userId) ?? 0;
    this.userFlags.set(userId, current | feature);
  }

  // 停用功能：AND NOT 清位
  disableFeature(userId: string, feature: FeatureFlag): void {
    const current = this.userFlags.get(userId) ?? 0;
    this.userFlags.set(userId, current & ~feature);
  }

  // 切換功能：XOR Toggle
  toggleFeature(userId: string, feature: FeatureFlag): void {
    const current = this.userFlags.get(userId) ?? 0;
    this.userFlags.set(userId, current ^ feature);
  }

  // 檢查是否啟用（支援組合查詢：是否同時啟用多項功能）
  hasFeature(userId: string, feature: number): boolean {
    const flags = this.userFlags.get(userId) ?? 0;
    return (flags & feature) === feature; // 必須全部啟用才回傳 true
  }

  // 取得所有已啟用的功能名稱
  getEnabledFeatures(userId: string): string[] {
    const flags = this.userFlags.get(userId) ?? 0;
    return Object.entries(Features)
      .filter(([, value]) => (flags & value) !== 0)
      .map(([key]) => key);
  }
}

// 使用範例
const service = new FeatureFlagService();
service.enableFeature("user1", Features.DARK_MODE);
service.enableFeature("user1", Features.NOTIFICATIONS);
service.enableFeature("user1", Features.PREMIUM);
// user1 的 flags = 0b010011 = 19

console.log(service.hasFeature("user1", Features.DARK_MODE));  // 輸出：true
console.log(service.hasFeature("user1", Features.ANALYTICS));  // 輸出：false

// 組合查詢：是否同時啟用 PREMIUM 和 AI_ASSISTANT
const PREMIUM_AI = Features.PREMIUM | Features.AI_ASSISTANT;
console.log(service.hasFeature("user1", PREMIUM_AI)); // 輸出：false（未啟用 AI）

console.log(service.getEnabledFeatures("user1"));
// 輸出：["DARK_MODE", "NOTIFICATIONS", "PREMIUM"]

// ━━ 陷阱：JavaScript 位元運算的 32-bit 限制 ━━
console.log(1 << 31);  // 輸出：-2147483648（符號位被設定！）
console.log(1 << 32);  // 輸出：1（移位量對 32 取模，等同 1 << 0）

// 正確：使用 >>> 確保邏輯右移（補 0 而非符號位）
function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1); // 取 n 最低位加入 result
    n >>>= 1; // 邏輯右移（確保補 0）
  }
  return result >>> 0; // 確保回傳無號整數的正確表示
}

// BigInt 用於超過 32 位的場景（子集枚舉 n > 30 時）
function enumerateSubsetsSafe(n: number): void {
  if (n > 30) {
    const total = BigInt(1) << BigInt(n);
    for (let mask = BigInt(0); mask < total; mask++) {
      // 使用 BigInt 操作（注意：BigInt 不能和 number 混用）
    }
  }
}

// NOT 運算的陷阱：~ 在 JS 中是負數
const x = 5; // 0b00000101
console.log(~x); // 輸出：-6（不是 250！）
// 原因：~5 = -(5+1) = -6（32 位有號整數取補數）

// 若要取 8-bit 的 NOT 結果：
const not8bit = (~x) & 0xFF;
console.log(not8bit); // 輸出：250 = 0b11111010 ✓

#include <vector>
#include <bitset>
#include <numeric>
#include <iostream>

// ━━━━━━━━━━ GCC/Clang 內建位元函式 ━━━━━━━━━━

void builtinDemo() {
    int n = 0b01101010; // 106

    // 計算 1 的個數（popcount）
    int ones = __builtin_popcount(n);       // 4（int 版本）
    int ones_ll = __builtin_popcountll(n);  // 4（long long 版本）

    // 計算末尾 0 的個數（Count Trailing Zeros）
    // lowbit(n) 的位置 = __builtin_ctz(n)
    int ctz = __builtin_ctz(n);             // 1（最低位 1 之前有 1 個 0）

    // 計算開頭 0 的個數（Count Leading Zeros），int 為 32 位
    int clz = __builtin_clz(n);             // 24（106 = 0x6A，高 24 位為 0）

    // 計算最高位 1 的位置（0-indexed from LSB）
    int highest = 31 - __builtin_clz(n);    // 6（第 6 位是最高的 1）

    std::cout << "popcount: " << ones << "\n";   // 輸出：4
    std::cout << "ctz: " << ctz << "\n";         // 輸出：1
    std::cout << "highest bit: " << highest << "\n"; // 輸出：6
}

// ━━━━━━━━━━ std::bitset（固定大小的位元陣列）━━━━━━━━━━

void bitsetDemo() {
    std::bitset<8> bs1("01101010"); // 從字串初始化
    std::bitset<8> bs2(0b10110100);

    // 基本操作
    bs1.set(0);   // 設第 0 位為 1
    bs1.reset(1); // 清第 1 位為 0
    bs1.flip(2);  // 切換第 2 位

    // 統計
    std::cout << bs1.count() << "\n"; // 輸出 1 的個數
    std::cout << bs1.size() << "\n";  // 輸出總位元數 = 8

    // 集合操作
    std::bitset<8> andResult = bs1 & bs2;
    std::bitset<8> orResult  = bs1 | bs2;
    std::bitset<8> xorResult = bs1 ^ bs2;

    // 效能優勢：bitset<1000000> 操作以 64 位 word 批次處理
    // 每次相當於處理 64 位 → 速度是逐位處理的 64 倍
    std::bitset<1000000> largeBitset;
    largeBitset.set();           // 全部設 1，O(n/64)
    std::cout << largeBitset.count() << "\n"; // 輸出：1000000
}

// ━━━━━━━━━━ 核心技巧（C++ 版）━━━━━━━━━━

class BitTricks {
public:
    // 判斷是否為 2 的冪
    bool isPowerOf2(int x) {
        return x > 0 && (x & (x - 1)) == 0;
    }

    // Brian Kernighan popcount
    int popcount(int n) {
        int count = 0;
        while (n) {
            n &= n - 1;
            count++;
        }
        return count;
    }

    // Single Number（LeetCode 136）
    int singleNumber(std::vector<int>& nums) {
        return std::reduce(nums.begin(), nums.end(), 0, std::bit_xor<int>());
    }

    // Sum of Two Integers（LeetCode 371）
    // 注意：有號整數左移可能是未定義行為（UB），轉型為 unsigned 避免
    int getSum(int a, int b) {
        while (b != 0) {
            unsigned carry = (unsigned(a) & unsigned(b)) << 1;
            a = a ^ b;
            b = static_cast<int>(carry);
        }
        return a;
    }

    // 枚舉 mask 的所有子集（子集 DP 關鍵）
    void enumerateSubsets(int mask) {
        for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
            process(sub);
        }
        process(0); // 空集
    }

private:
    void process(int sub) {
        // 處理子集 sub 的邏輯
    }
};

// ━━━━━━━━━━ LeetCode 338 Counting Bits（C++ 版）━━━━━━━━━━

std::vector<int> countBits(int n) {
    std::vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
}

// dp[mask][i] = 訪問了 mask 中所有城市、目前在城市 i 的最短路徑
// mask 的每個位元代表對應城市是否已訪問
function tsp(dist: number[][]): number {
  const n = dist.length;
  const INF = Infinity;
  const FULL = (1 << n) - 1; // 所有城市都訪問的狀態

  const dp: number[][] = Array.from({ length: 1 << n }, () =>
    new Array(n).fill(INF)
  );
  dp[1][0] = 0; // 從城市 0 出發，mask = 0b0001

  for (let mask = 1; mask <= FULL; mask++) {
    for (let u = 0; u < n; u++) {
      if (dp[mask][u] === INF) continue;
      if (!((mask >> u) & 1)) continue; // 城市 u 必須在 mask 中

      // 嘗試前往未訪問的城市 v
      for (let v = 0; v < n; v++) {
        if ((mask >> v) & 1) continue; // 城市 v 已訪問，跳過
        const newMask = mask | (1 << v);
        dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + dist[u][v]);
      }
    }
  }

  // 找回到起點（城市 0）的最短總路徑
  let ans = INF;
  for (let u = 1; u < n; u++) {
    if (dp[FULL][u] !== INF) {
      ans = Math.min(ans, dp[FULL][u] + dist[u][0]);
    }
  }
  return ans;
}

// ━━ 找兩個不重複的數（LeetCode 260）━━
// 擴展自 Single Number，利用 lowbit 將陣列分兩組
function singleNumberIII(nums: number[]): number[] {
  const xorAll = nums.reduce((acc, n) => acc ^ n, 0); // a ^ b
  const bit = xorAll & (-xorAll); // a 和 b 在此位元上不同的 lowbit
  let a = 0;
  for (const n of nums) {
    if (n & bit) a ^= n; // 此位元為 1 的一組，XOR 得到 a
  }
  return [a, xorAll ^ a]; // 另一個數 = a ^ (a ^ b) = b
}

// ━━ 格雷碼（Gray Code）生成 ━━
// 相鄰格雷碼只差 1 個位元，應用於旋轉編碼器、錯誤更正碼
function grayCode(n: number): number[] {
  const result: number[] = [];
  for (let i = 0; i < (1 << n); i++) {
    result.push(i ^ (i >> 1)); // 二進位轉格雷碼公式
  }
  return result;
}
// grayCode(3) → [0,1,3,2,6,7,5,4]
// 二進位：000,001,010,011,100,101,110,111
// 格雷碼：000,001,011,010,110,111,101,100

// ━━ XOR Checksum（簡單資料完整性驗證）━━
function xorChecksum(data: number[]): number {
  return data.reduce((acc, x) => acc ^ x, 0);
}
// 傳輸後重新計算 checksum，若與原始相同表示資料完整

class FilePermission {
  // 權限位元常數（八進位表示）
  static readonly S_IRUSR = 0o400; // owner read
  static readonly S_IWUSR = 0o200; // owner write
  static readonly S_IXUSR = 0o100; // owner execute
  static readonly S_IRGRP = 0o040; // group read
  static readonly S_IWGRP = 0o020; // group write
  static readonly S_IXGRP = 0o010; // group execute
  static readonly S_IROTH = 0o004; // others read
  static readonly S_IWOTH = 0o002; // others write
  static readonly S_IXOTH = 0o001; // others execute

  private mode: number;
  constructor(mode: number = 0o644) { this.mode = mode; }

  hasPermission(perm: number): boolean { return (this.mode & perm) !== 0; }
  addPermission(perm: number): void    { this.mode |= perm; }
  removePermission(perm: number): void { this.mode &= ~perm; }
  togglePermission(perm: number): void { this.mode ^= perm; }
}

const perm = new FilePermission(0o755); // rwxr-xr-x
console.log(perm.hasPermission(FilePermission.S_IXUSR)); // 輸出：true
perm.removePermission(FilePermission.S_IXGRP | FilePermission.S_IXOTH);
// mode 變為 0o744（rwxr--r--）

// 陷阱 1：XOR Swap 在相同位置使用會清零
function xorSwapBad(arr: number[], i: number, j: number): void {
  // 若 i === j：
  arr[i] ^= arr[j]; // arr[i] ^= arr[i] = 0  ← 資料遺失！
  arr[j] ^= arr[i];
  arr[i] ^= arr[j];
}
// 修正：先判斷 if (i === j) return;

// 陷阱 2：子集枚舉時空集漏掉
function enumerateSubsetsBad(mask: number): void {
  for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // 當 sub = 0 時迴圈終止，空集 {} 未被處理！
    process(sub);
  }
  // 修正：迴圈後加 process(0);
}

// 陷阱 3：C++ 有號整數左移溢位是未定義行為（UB）
// int a = 1;
// int bad = a << 31;  // UB！
// unsigned safe = 1u << 31;  // 安全：轉為 unsigned 再移位

function process(sub: number): void {}

// 方法 1：Brian Kernighan 算法（最優雅）
function hammingWeightBK(n: number): number {
  let count = 0;
  while (n !== 0) {
    n &= n - 1; // 清除最低位的 1，每次迭代減少一個 1
    count++;
  }
  return count;
}

// 方法 2：逐位掃描（直觀但固定 32 次）
function hammingWeightBit(n: number): number {
  let count = 0;
  for (let i = 0; i < 32; i++) {
    if ((n >>> i) & 1) count++; // 使用 >>> 確保邏輯右移
  }
  return count;
}

// 方法 3：JavaScript 的奇技（parseInt + split）
// 僅供了解，競程中請用 Brian Kernighan
function hammingWeightString(n: number): number {
  return (n >>> 0).toString(2).split('').filter(c => c === '1').length;
}

console.log(hammingWeightBK(11));  // 輸出：3（11 = 0b1011，三個 1）
console.log(hammingWeightBK(128)); // 輸出：1（128 = 0b10000000，一個 1）

// Bitmask 版本：最簡潔，面試首選
function subsets78(nums: number[]): number[][] {
  const n = nums.length;
  const result: number[][] = [];

  for (let mask = 0; mask < (1 << n); mask++) {
    const subset: number[] = [];
    for (let i = 0; i < n; i++) {
      if ((mask >> i) & 1) {
        subset.push(nums[i]);
      }
    }
    result.push(subset);
  }

  return result;
}

// 回溯版本（另一種常見解法，便於比較）
function subsets78Backtrack(nums: number[]): number[][] {
  const result: number[][] = [];

  function backtrack(start: number, current: number[]): void {
    result.push([...current]);
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }

  backtrack(0, []);
  return result;
}

// 兩種方法的複雜度相同：O(2ⁿ × n)（共 2ⁿ 個子集，每個最多 n 個元素）
console.log(subsets78([1, 2, 3]));
// 輸出：[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]