位运算妙妙屋

摘要：
位运算使用技巧。

1. int类型利用位运算乘除2的k次幂

a乘以2的k次幂，相当于a << k 不管a是否为正数。
a除以2的k次幂，相当于a >> k 当且仅当a为正数。
注意，其他类型不常用，有的可以有的不可以，故不列出。

2. 判断二进制数的第k位

首先明确第k位是指从右边最低位向左边最高位第k位。注意低位是从0开始计算，这样也是方便适配左移右移位数。和循环计数一般从0开始一个道理。
代码为：

1
2
3

int x;
int m;
m = x >> k & 1;

右移k位就把第k位移到了最低位，再判断该位置数字。

3. 二进制数最后一位1的————lowbit(x)

这里最后一位1是从左往右最后一位，也就是指最低位1，函数lowbit()返回的是包含该1与右边所有0。

1
2
3

int lowbit(int x) {
    return x & - x;
}

- x 在计算机内部是以补码方式运算的，即:
- x = ~ x + 1
假设一个二进制数为： 0010101…0010100000
~ x为： 1101010…1101011111
~ x + 1为： 1101010…1101100000
注意到+1操作使得最后一位1及其右边所有数字发生了变化，而左边不变。
此时在和原数字进行&运算，它和原数字在最后一位1左侧全部不同，右侧全部相同。

参考题目： 二进制中1的个数

4. 一个获取二进制数中1的个数的轮子

在c++中：
__builtin_popcount(unsigned int x)
用于计算一个32位无符号整数有多少个位为1。
类似地，可以用 __builtin_popcountl(unsigned long x) 和 __builtin_popcountll(unsigned long long x) 分别计算无符号 long 和 long long 整数二进制表示中1的位数。

在Java中：
Integer.bitCount(int x)

更多计算二进制表示的数中数字1的个数： 位1的个数

5. 二进制数中最高位1距离最低位的距离

int get_len(int x) {
    int len = 0;
    for (; x; len ++) x >>= 1;
    return len;
}

参考题目： LeetCode 5620. 连接连续的二进制数字

6. 两个数之间交换位置

我们有int a = 5, int b = 6, 现需要交换二者位置，可以利用异或运算：

1
2
3

a = a ^ b;
b = a ^ b;
a = a ^ b;

7. 实现加法运算

现有int a和int b，用位运算实现加法运算。
可以用a ^ b计算无进位加，用a & b << 1计算进位。
二者递归相加即可得到a + b的值。
举例：
int a = 8, int b = 13；
8的二进制补码为：1000
13为：1101
a和b的无进位加为：1000 ^ 1101 = 0101
a和b的加法进位为：1000 & 1101 = 10000
接着，我们递归地用上述方法计算0101和10000的和，直到进位为0.

class Solution {
public:
    int Add(int num1, int num2)
    {
        if (!num2) return num1;
        
        int sum = num1 ^ num2;
        int carry = (unsigned int)(num1 & num2) << 1;
        
        return Add(sum, carry);
    }
};

注意，c++支持负数左移，都是存的补码，int会越界所以转为unsigned int

8. 二进制数记录单词中出现过的字符

记录一个仅由全部大写字母或全部小写字母构成的单词中出现过的字符，因为最多出现26种字符，可以用一个32位 int 数字统计字符是否出现过。
从数字最低位开始，对应 'a' 或 'A'。对于字符 c，可以用 1 << c - 'a' 或 1 << c - 'A' 在对应位置设 $1$.

将单词所有字符进行如上操作，将全部结果进行或运算得到的最终数字就可以记录单词中出现过的字符。
参考题目： LeetCode 318. 最大单词长度乘积

9. 异或运算性质

$a \bigoplus 0 = a$
$a \bigoplus a = 0$
$(a \bigoplus b) \bigoplus c = a \bigoplus (b \bigoplus c)$
$a \bigoplus b = b \bigoplus a$
如果 $a \bigoplus b = c$
则 $b = a \bigoplus c$
，这是一种加密算法。

10. 一个二进制数 $x$，它的距离最低位 $k$ 个数字不同且其他位相同的二进制数为：

x ^ (1 << k)

11. 二进制快速幂

详见【AcWing算法基础】第四讲-数学知识-快速幂 AcWing 875. 快速幂