位运算符

程序中的所有数字在计算机内存中都是以二进制的方式储存的，位运算的实质，就是直接对整数在内存中的二进制位进行操作。

比如，and运算符本来是一个逻辑运算符，但整数与整数之间也可以进行and运算，举个例子，6的二进制形式为110，11的二进制是1011，则6 and 11的结果就是2。（0表示false，1表示true，空位作0）

由于位运算符直接对内存数据进行操作，不需要转换成十进制，因此处理速度非常快。这一讲会了解位运算的一些经典应用，以及如何用位运算优化程序

算数移位与逻辑移位

上图所示为常见的一些位运算操作符及其作用

以亦或（XOR）为例，介绍一下其常见操作：

x ^ 0 = x
X ^ 1s =~x // 1s = ~0
X ^ (~X) = 1s 
x ^ x = 0 // interesting and important !
a ^ b = c => a ^ c = b, b ^ c = a // 可用于交换a、b
a ^ b ^ c = a ^ ( b ^ c ) = (a ^ b) ^ c // 结合律

位运算的应用

编程实践中常用的位运算操作：

X & 1 == 1 OR == 0 判断奇偶（x % 2 == 1）
X = X & (X-1) => 清零最低位的1(x-1的变化是最低位1变0，后面0全部变1，再与X相于又变回0)
X & -X => 得到最低位的1
X & ~X => 0
x << n => x*2ⁿ

更为复杂的位运算操作：

将x最右边的n位清零：x &(~0<< n)
获取x的第n位值(0或者1)：(x>>n)&1
获取X的第n位的幂值：x&(1<<(n-1))
仅将第n位置为1：x| (1<<n)
仅将第n位置为0：x &(~(1 << n))
将x最高位至第n位(含)清零：x&((1<<n) - 1)
将第n位至第0位(含)清零：x&(~((1<<(n+1))-1))

实战题目

统计位1的个数输入是无符号整数x，输出二进制表达式中1的个数count
- 思路一：直接枚举二进制数位数。不断用x%2==1（x&1==1）判断最后一位是不是1，是1则count++。用x=x>>1移位。时间上与数字长度成正比，复杂度O(1)
```
def hammingWeight(self, n):
rst = 0
mask = 1
for i in range(32):
   if n & mask:
       rst += 1
   mask = mask << 1
return rst
```
- 思路二：在x!=0前提下不断用x = x & (x-1)来去除最低位的1，循环了几次count就是多少
```
int hammingWeight(uint32_t n){
int res = 0;
for( ; n; n &= n-1)
   ++res;
return res;
}
```
比特位计数上一题的升级版，给定整数n，返回从0到n每个数的二进制表达式中有多少1
- 思路一：用上一题的思路，从0到n循环调用hamingweight方法赋值
- 思路二：根据“递推公式”即数学规律进行计算。用一个数组count下标为i的元素count[i]推导i+1的二进制表达式中1的个数count[i+1]，则count[i]=count[i>>1]+i&1。此公式原理在于数i二进制表达式中1的位数，取决于数i-1二进制表达式中1的位数和i是否为偶数。
```
vector<int> countBits(int num){
vector<int> bits(nums+1, 0)；
for(int i=1;i<=num;i++){
   bits[i]=bits[i >> 1]+i&1;
}
return bits;
}
```
2的幂次方问题若输入参数x是2ⁿ，则返回true，否则返回false
- 思路一：不断执行x = x / 2，若最后有余数，则返回false
- 思路二：使用内置函数，即y=log₂x，若x是2的幂次方则y是整数
- 思路三：使用x= x&(x-1)去除最后一位，看结果是否为0，若为0则返回true
  - c版：
```
bool isPowerOfTwo(int n){
return n > 0 && !(n & (n-1));
}
```
  - Python版：
```
def isPowerOfTwo(self, n):
return n > 0 and not (n & n-1)
```
N皇后问题另一种解法
- 背景回顾：n个皇后放置在n*n的的棋盘上，各皇后之间彼此不能互相攻击。之前的方式是朴素的DFS，按行进行搜索，每一层搜索可以放在哪一列，通过col[n]、row[n]、pie[n]和na[n]来判断是否可发生攻击。
- 用位运算优化和改进，主要是对DFS中搜索行、列、撇得到空位这一过程进行加速。
```
def totalNQueens(self, n):
if n < 1: return[]
self.count = 0
self.DFS(n, 0, 0, 0, 0) 
return self.count
def DFS(self, n, row, cols, pie, na):
# recursion te rminator
if row >= n:
   self.count += 1
   return

bits=(~(cols|pie|na))&((1<<n)-1)#当前所有的空位

while bits:
p=bits & -bits#取到最低位的1
self.DFS(n,row+1,cols|p,(pie|p)<<1,(na|p)>>1)
bits=bits&(bits-1)#去掉最低位的1
```
  上面一段代码中，最关键的部分就是bits=(~(cols|pie|na))&((1<<n)-1),这步先是三维变量相或取反，再与1左移n位得到的值相与，结果是前面全为0，后面n位的二进制位，这里面的1表示可以放皇后

位运算

位运算符

算数移位与逻辑移位

位运算的应用

实战题目

results matching ""

No results matching ""