常用的位运算

位运算符

符号	含义	特点
&	按位与	都为 1 才是 1
`	`	`
^	按位异或	相同为 0，不同为 1
~	按位取反	0 变 1，1 变 0
<<	左移	低位补 0
>>	右移（算术）	高位补符号位
>>>	无符号右移	高位补 0

判断奇偶

(n & 1) == 0  // 偶数
偶数：xxxx0 & 0001 = 0
奇数：xxxx1 & 0001 = 1

判断是否为2的幂

n & (n - 1) = “消灭最低位的 1”。如果能一消就没了，说明它只有一个 1（就是 2 的幂）。

(n>0)&&((n&(n-1))==0)
//例如：n = 5
  n   = 101
& n-1 = 100
-----------
        100
//结果不为0，所以不是2的幂
//例如：n = 4
  n   = 100
& n-1 = 011
-----------
        000
//结果为0，所以是2的幂

计算2的n次幂

// 计算 2^n
int power2(int n) {
    return 1 << n;
}

取某一位

第几位：从0开始从右往左数

(n & (1 << k)) != 0
例如: k = 3 n = 10

       n  = 1010
&  1 << 3 = 1000
------------------
		    1000
1000 != 0所以1010的第3位是1

设置某一位为1

n |= (1 << k)
例如：
k = 2   → 1 << 2 = 00000100
    n  = 10110110
1 << 2 = 00000100
n |= 10110110  (第 2 位变成 1)

交换两个数

利用异或的性质 a ^ b ^ b = a

// 不使用额外变量交换a和b
void swap(int a, int b) {
    a = a ^ b;
    b = a ^ b;  // b = (a^b) ^ b = a
    a = a ^ b;  // a = (a^b) ^ a = b
}

快速幂

long quickPow(long base, int exp) {
    long result = 1;
    while (exp > 0) {
        if ((exp & 1) == 1) {  // 指数为奇数
            result *= base;
        }
        base *= base;
        exp >>= 1;  // 指数除以2
    }
    return result;
}