c++ 位操作集合

位運算在很多時候可以發揮出強大的威力， 尤其在需要狀态壓縮的算法題裡面

// 位操作合集

// 最左的 1 的位置
int leftOneIndex(unsigned int val) {
    if (val == 0) {
        return -1;
    }
    return 31 - __builtin_clz(val);
}

// 最右1的位置
int rightOneIndex(unsigned int val) {
    if (val == 0) {
        return -1;
    }
    return __builtin_ffs(val) - 1;
}

// 二進制1的個數
int oneCount(unsigned int val) {
    return __builtin_popcount(val);
}

using func = function<int()>;

// 下一個1的位置, 從低位開始到高位
auto nextRightOneIndex(unsigned int val) -> func {
    return [value = val]() mutable -> int {
        int p = rightOneIndex(value);
        if (p != -1) {
        	value ^= (1 << p);
        }
        return p;
    };
}

int main() {
    auto v = nextRightOneIndex(7);
    int p;
    while ((p = v()) != -1) {
        cout << p << endl;
    }
}
           

位操作
1. 得到最右 1
a & (-a) 
或者  a &  (~（a - 1）)
-a = ~(a - 1)

2. 得到 1的個數
a & (a - 1) 的次數

3   對于負數  (a - 1)  ^ -1 = abs(a)
絕對值
int abs(int x) {
int y = x >> 31;
return (x - 1)  ^ y;
}

4. x 為負數則
~（x - 1） = (x - 1) ^ (-1)