位运算

两数之间的运算符

• 两数的运算符有 「与，或，异或」三种运算方式，它们都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。

运算	运算符	数学符号	解释
与	&	$\&,and$	只有两个对应位都为 1 时才为 1
或	|	$\mid ,or$	只要两个对应位中有一个 1 时就为 1
异或	^	$\oplus ,xor$	只有两个对应位不同时才为 1

一些总结经验：

• 对或(|)运算而言，有如下性质：

  • $a\mid b=b\mid a$
  • $\left(a\mid b\right)\mid c=\left(b\mid c\right)\mid a$
  • $a\mid 0=a$
  • $a\mid a=a$
  • 若 $a\le b$，则 $a\mid c\le b\mid c$（对无符号数成立)
  • $a\mid b\le \max (a,b)$

• 对异或 $\oplus$ 有如下性质：

  • $a\oplus b=a+b-2(a\&b)$
  • $a\oplus b=x\Rightarrow a=b\oplus x$