1. 位运算
1.1. 技巧
- 位运算交换两个数
function swap(&$a, &$b) {
$a ^= $b;
$b ^= $a;
$a ^= $b;
}
- 位移实现乘除法
$a >> 1 除以2
$a << 1 乘以2
- 判断奇偶性
($a & 1) === 0 偶数
- 位操作交换符号
$a = ~$a + 1
- 位操作求绝对值
function abs($a) {
$i = $a >> 31; // 获取符号位
return $i === 0 ? $a : (~$a + 1); // 符号位=1则转换符号
}
- 位操作进行高低位交换
16位的无符号数, 高8位与低8位交换: $a >> 8 | $a << 8
位操作进行二进制逆序
位操作中统计二进制1的个数
function countBit($a) {
$count = 0;
while($a) {
$a &= ($a - 1); // 消去最后一位1
$count++;
}
return true;
}
- 将二进制数的最后一个1置为0
$a & ($a - 1)
- 检查 n 是否为 2 的幂次
因为2的幂次在二进制表示中只有一个1, 应用上一个技巧, 判断消去一个1后是否为0即可
return $a & ($a - 1) === 0;
- 如果将整数 A 转换为 B, 需要改变多少个 bit?
思路与9类似, $a ^ $b 的结果中1的数量即为不同的位数, 也就是需要改变的bit数量
$a ^ $b ^ $b = $a
12.1 数组中, 只有一个数出现了一次, 剩下的都出现了两次, 找出只出现了一次的数
所有数异或, 得到的就是只出现了一次的数
12.2 数组中, 只有一个数出现一次, 剩下的都出现三次, 找出出现一次的
12.3 数组中, 只有两个数出现一次, 剩下的数都出现两次, 找出出现一次的
$res = $x ^ $y, 那么可以根据二进制中的某一位是不是1将数分为两组, $x, $y 分别在这两个组中.
1.2. 与 &
两数间的运算
对二进制表示的数的每一位逐一运算
1 & 1 = 1; 1 & 0 = 0; 0 & 0 = 0;
两整数 a, b, a ^ b 是无进位的相加
1.2.1. 快速判断数是否为2的幂
2的幂在二进制中只有一个1 非2的幂有一个以上的1 原理: -x = ~x + 1, x & (-x) = x & (~x + 1) = 保留最右边的1
($n & -$n) === $n;
1.3. 或 |
1 | 1 = 1; 1 | 0 = 1; 0 | 0 = 0;
1.4. 异或 ^
两位不为相同时才为1
异或的逆运算为本身: a ^ b ^ b = a
1 ^ 1 = 0; 1 ^ 0 = 1; 0 ^ 0 = 0;
通常用来求数组中只出现一次的数字的问题.
a,b 整数, a&b 得到每一位的进位
交换律：a ^ b ^ c <=> a ^ c ^ b
任何数于0异或为任何数 0 ^ n => n
相同的数异或为0: n ^ n => 0
1.5. 取反 ~
对一个数的操作, 将二进制数的每一位取反
-x = ~x + 1
1.6. 左移 <<
乘以2
将二进制数左移i位得到的值, 右侧将填0,
1.7. 右移 >>
除以2
将二进制数右移i位得到的值, 右侧多余的数会被舍弃.
无符号数将在左侧填0; 有符号数将依据符号位决定左侧补0还是补1, 符号位将随着移动
1.8. 补码
整数的补码是本身
负数的补码需要将除符号位之外的位都置反, 然后+1
1.9. 加法位移实现 加减乘除求余运算
1.9.1. 加法
各位相加进位即可
1.9.2. 减法
15 - 10, 会将 10 的二进制 00001010 变为 -10 11110101, 最高位为符号, 然后 00001111(15) + 11110110(10) = 000000101(5)