位运算

位运算概述

• 计算机以二进制储备，只存在 \(1,0\) 两种状态
• 计算机对于二进制数据的运算叫位运算

按位于运算符（&）

• 两数同时为 \(1\),答案是 \(1\),否则结果是 \(0\)

用途

1.清零

一个数清零，就将其二进制数与 \(0\) 相与，结果为零

2.取一个数的指定位置

如果想取出某一数二进制下的后几位，则可以将其与 \(Y\) 相与，\(Y\) 的定义是要求的位数为 \(1\)

3.判断奇偶

最后一位是 \(1\) 为奇数，\(0\) 则为偶数。因此可以

if ( ( a & 1 == 0 ) )

---

或运算（|）

• 简单说就是不进数相加，不一样就为1

用途

更改位置为 \(1\)

将要求的位数改成1，就可以与一个要求位数为 \(1\) 数相或，即可完成更改

---

异或与算符（^）

• 两两相同为 \(0\)，不同为 \(1\)

性质

1. 交换律
2. 结合律 \((a\ xor\ b)xor\ c = a\ xor\ (b\ xor\ c)\)
3. 对于任何数 x ，都有 \(a\ xor\ a = 0\ ,\ a \ xor\ 0 = a\)
4. 自反性 \(a\ xor\ b\ xor\ b=a\ xor\ 0=a\)

用途

1.翻转指定位

与一个指定位数位 \(1\) 的数相异或，即可

2.与 \(0\) 异或值不变

同性质3

3.交换两个数

void Swap(int &a, int &b){
    if (a != b){
        a ^= b;
        b ^= a;
        a ^= b;
    }
}

---

综合使用

\[a+b=((a\&b)<<1)+(a\ xor\ b) \]