HDU 1196 Lowest Bit：位運算技巧

問題描述

給定正整數 A (1 ≤ A ≤ 100)，輸出其二進制表示中最低位的 1 所代表的值（即 A & -A）。輸入以 0 結束，0 不處理。

例如：
A = 26 (二進制 11010) → 最低位 1 在第 1 位（從 0 計數），值為 2。
A = 88 (二進制 1011000) → 最低位 1 在第 3 位，值為 8。

核心原理：A & -A

在二進制補碼表示中，-A = ~A + 1。A 與 -A 按位與，只會保留 A 最低位的 1，其餘位均為 0。這是經典位運算技巧。

證明：設 A = x 1 0...0（最低位 1 後全為 0），則 -A = ~x 0 1...1 + 1 = ~x 1 0...0。A & -A = 0...0 1 0...0，即最低位 1 對應的 2 的冪次。

算法流程

1. 循環讀入 A，直到 0。
2. 計算 lowbit = A & -A（或 A & (~A + 1)）。
3. 輸出 lowbit。

代碼實現（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int A;
    while (cin >> A && A) {
        cout << (A & -A) << '\n';
    }
    return 0;
}

替代寫法（不使用負數）

int lowbit(int x) {
    return x & (~x + 1);
}
// 或手動計數尾部 0
int lowbit_manual(int x) {
    int cnt = 0;
    while ((x & 1) == 0) {
        x >>= 1;
        ++cnt;
    }
    return 1 << cnt;
}

複雜度分析

時間 O(1) 每查詢，空間 O(1)。極其高效。

應用拓展

lowbit 是樹狀數組、二進制索引樹、子集枚舉等算法的核心操作，值得熟練掌握。