位运算

1.1. 技巧 位运算交换两个数 function swap(&$a, &$b) { $a ^= $b; $b ^= $a; $a ^= $b; } Copy 位移实现乘除法 $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 则转换符号 } Copy 位操作进行高低位交换 16 位的无符号数, 高 8 位与低 8 位交换: $a >> 8 | $a << 8

位操作进行二进制逆序

位操作中统计二进制 1 的个数

function countBit($a) { $count = 0; while($a) { $a &= ($a - 1); // 消去最后一位 1 $count++; } return true; } Copy 将二进制数的最后一个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; Copy 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)

1.9.3. 乘法