位运算的运用(Bitwise operations)
- 位运算符
- 算数移位与逻辑移位
- 位运算的应⽤
什么是位运算
程序中的所有数在计算机内存中都是以二进制的形式储存都。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如， and 运算本来是一个逻辑运算符，但是整数与整数之间也可以进行 and 运算。举个例子， 6 的二进制是 110，11 的二进制是 1011， 那么 6 and 11 的结果为 2， 它是二进制对应位进行逻辑运算的结果（0 表示 false, 1 表示 true， 空位都当 0 处理）
110 AND 1011 --> 0010(b) --> 2(d)
由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。当然有人说，这个快了有什么用，计算 6 and 11 没有什么实际意义啊。那么位运算到底可以干什么，有什么经典应用，以及如何用位运算优化你的程序。
编程常用的位运算操作
X & 1 == 1 OR == 0
X = X & (X-1) => 清零最低位的 1
X & -X => 得到最低位的 1
X & ~X => 0
位运算操作
- X & 1 == 1 OR == 0 判断奇偶 (X % 2 == 1)
- X = X & (X-1) => 清零最低位的 1
- X & -X => 得到最低位的 1
不同编程语言的语法问题
- Python: x, y = 1, 2
- Java or C++: x=1; y=2;
- Python: x, y = y, x (可以有效实现交换两数)
- Java or C++: int tmp = x; x = y; y = tmp;
实战题⽬
- https://leetcode.com/problems/number-of-1-bits/
- https://leetcode.com/problems/power-of-two/
- https://leetcode.com/problems/counting-bits/description/
- https://leetcode.com/problems/n-queens-ii/description/