1.概念

位运算就是 直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中使用位运算操作会大大提高程序的性能。

---

2.常用的运算符

1. $\&$(与) 运算规则：两个二进制位都为1时，结果才为1

   例：0001&0100 = 0000，即$1 \& 4 = 0$

2. $|$(或) 运算规则：两个位都为0时，结果才为0

   例：0101|0001 = 0101，即$5 | 1 = 5$
   

3. $<<$(左移) 运算规则：各二进制位全部左移若干位，高位丢弃，低位补0

   例：0001<<2 = 0100，即$1 << 2 = 4$
   

4. $>>$(右移) 运算规则：各二进制位全部右移若干位，对无符号数，高位补0，有符号数，高位补1

   例：0100>>2 = 0001，即$4 >> 2 = 1$
   

5. ∧ (异或) 运算规则：两个二进制位相同为0，相反为1

   例：0101 ^ 0110 = 0011，即5 ^ 6 = 3
   

6. ~ (取反) 运算规则：0变1，1变0

   例：~0 = 1

---

3.运算律

公式名称	运算规则
交换律	$A \& B = B \& A, A ∧ B = B ∧ A$
结合律（注意结合律只能在同符号下进行）	$(A \& B) \& C = A \& (B \& C)$
等幂律	$A \& A = A,A | A = A$
零律	$A \& 0 = 0, A | 1 = 1$
互补律（注意，这不同于逻辑运算）	$A \&$~A$= 0$, $A |$~A$= -1$
同一律	$A | 0 = A, A ∧ 0 = A$

---

• 异或运算常用的运算律

名称	运算规则
交换律	$a⊕b=b⊕a$
结合律	$a⊕(b⊕c) = (a⊕b)⊕c$
归零律	$a⊕a=0$
恒等律	$a⊕0=a$
自反性	$a⊕b⊕b=a$

---

4.高级操作

1. 去掉最低位的二进制数： $x >> 1$

   例：$x = 0100，x >> 1 = 0010$

2. 在最低位增加一个0：$x << 1$

   例：$x = 0100，x << 1 = 1000$

3. 取末k位：$x \&(1 << k - 1)$

   例：$x = 1011，k = 2$，

   $x \&(1 << k - 1)=0011$

---

5.应用

1. 实现乘除法 x << 1 等价于 x * 2，x >> 1 等价于 x / 2

   例：$x = 15，x << 1 = 30，x >> 1 = 7$
   

2. 判断奇偶性：$x \& 1$ 奇数$\&1$的结果为1，偶数$\&1$的结果为0

   例：$x = 15，x \& 1 = 1$

   原理：偶数，无论是正整数还是负整数，二进制表示时其最低位为0；奇数，无论是正整数还是负整数，二进制表示时其最低位都为1
   

3. 判断最低二进制位是0还是1：$x\&1$

   $x\&1 = 0$，则最低二进制位为0；$x\&1 = 1$，则最低二进制为1

   实例：

   #include<iostream>
   using namespace std;
   int main()
   {
      int x = 15;//二进制:1111 
      if(x & 1)
    	  cout << "15的最低二进制为1" << endl;
      else
    	  cout << "15的最低二进制为0" << endl;
   }
   

   

4. 交换两个整数：

void swap(int &a, int &b){
   a ^= b;
   b ^= a;
   a ^= b;
}

实例：

#include<iostream>
using namespace std;
void swap(int &a, int &b)
{
   a ^= b;
   b ^= a;
   a ^= b;
}
int main()
{
   int a = 14, b = 20;
   swap(a, b);

   cout << "交换后a的值为:" << a << endl;
   cout << "交换后b的值为:" << b << endl;
   return 0;
}

证明: 对于$a = a ∧ b$，则$b = b ∧ ( a ∧ b )$ ，根据交换律、结合率以及恒等律，得$b = b ∧ ( b ∧ a ) = (b ∧ b) ∧ a = 0 ∧ a = a$

---

6.lowbit函数

1. lowbit函数介绍 lowbit(x)通常与树状数组一起使用，它的作用是返回x在二进制中最低为1所对应的值

   例：5 ->101，lowbit（5）= 1（1），

   12 -> 1100 ，lowbit（12）= 4（100）

   
   

2. 实现

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

   12（1100），-12（0100），lowbit（12）= 4

   原理，二进制数的负数是正数取反加一

3. lowbit函数的应用

• 统计1的个数

  实现：

  #include<iostream>
  using namespace std;//求x的二进制数中有多少个1
  int lowbit(int x)
   {
      return x & -x;
   }
  int count(int x)
  {
     int ans = 0;//ans记录x的二进制数中有多少个1
     while(x)
     {
        x -= lowbit(x);
        ans++;//个数+1
     }
     return ans;
  }
  

  实例：

  #include<iostream>
  using namespace std;//求x的二进制数中有多少个1
  int lowbit(int x)
  {
     return x & -x;
  }
  int count(int x)
  {
     int ans = 0;//ans记录x的二进制数中有多少个1
     while(x)
     {
        x -= lowbit(x);
        ans++;//个数+1
     }
     return ans;
  }
  int main()
  {
     cout << "12的二进制数中有" << count(12) << "个1";
     return 0;
  }