基本算法-01位运算 学习笔记

一、基本运算

1.按位与运算

按位与运算符"&"是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时，结果位才为1，否则为0。参与运算的数以补码方式出现。

按位与的两种经典应用:

• 让某一位或某些位为0 : X & 0XFE
• 取一个数中的一段 : X & 0XFF

2.按位或运算

按位或运算符“|”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的二个二进位有一个为1时，结果位就为1。参与运算的两个数均以补码出现。

按位或的两种经典应用：

• 使得一位或几个位为1 : X | 0X01(使最低位为1)
• 把两个数拼起来 : 0X00FF | 0XFF00 = 0XFFFF

3.按位异或运算

按位异或运算符“^”是双目运算符。其功能是参与运算的两数各对应的二进位相异或，当两对应的二进位相异时，结果为1，否则为0。

4.求反运算

求反运算符～为单目运算符，具有右结合性。其功能是对参与运算的数的各二进位按位求反。

5.左移运算

左移运算符“<<”是双目运算符。其功能把“<< ”左边的运算数的各二进位全部左移若干位，由“<<”右边的数指定移动的位数，高位丢弃，低位补0

• 将一个数左移n位，则得到该数与2的n次方的积，即 X <<= 2 <=> x *= 2^n

6.右移运算

右移运算符“>>”是双目运算符。其功能是把“>> ”左边的运算数的各二进位全部右移若干位，“>>”右边的数指定移动的位数。

• 算术右移等于除以2向下取整
• 将一个数右移n位，则得到该数与2的n次方的商，即 X <<= 2 <=> x /= 2^n

二、算法技巧

1.状态压缩

二进制状态压缩：将一个长度为m的bool数组用一个m位二进制整数表示并储存的方法。

利用下列位运算操作可以实现原bool数组中对应下标元素的存取

• 取出整数x在二进制表示下最低位的1所对应的值(lowbit运算)

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

• 取出整数x在二进制表示下的第k位

inline int getk(int x){
  return (x >> k) & 1;
}      

• 取出整数x在二进制表示下的第0~k - 1位(后k位)

inline int get(int x){
  return X & ((1 << k) - 1);
}      

• 把整数x在二进制表示下的第k位取反

inline int getk(int x){
  return x ^ (1 << k);
}      

• 把整数x在二进制表示下的第k位赋值为1

inline int getk(int x){
  return x | (1 << k);
}      

• 对整数x在二进制表示下的第k位赋值0

inline int getk(int x){
  return x & (~(1 << k));
}      

2.成对变换

通过计算总结：

1. 当n为偶数时，n ^ 1 = n + 1
2. 当n为奇数时，n ^ 1 = n - 1