基础操作

与运算:&

或运算:|

非运算:~x(按位取反)

异或运算:^ 1.a^a=0 2. 0^a=a

移位运算: 负数移位运算的时候高位会补1
\begin{equation} 1<<n = 2^n\end{equation}

\begin{equation} n>>x = \cfrac{n}{2^x}\end{equation}

补码:
负数:按位取反+1 \begin{equation}-x=~x+1(x的负数)\end{equation}
正数:本身是自己的补码

初始化整个数组为正无穷memset(f,0x3f,sizeof f)

常用操作

• 异或操作符合交换律和结合律,因此如果数字重复出现偶数次最后可异或成0,此时如果有一个数只出现1次,那么所有数异或最后会等于只出现一次的数 Acwing73.数组中只出现一次的两个数字
• n&-n从低位开始的第一个1AcWing26.二进制中1的个数  
  -n=~n+1,取反导致其每位都跟n&的结果为0,然而+1可以让n低位开始的第一个1的位置得到1的进位由0变1,就只有该位与n相同,所以可以返回低位开始的第一个1
• lowbit(x):返回x的从低位开始的第一个1(得到的是二进制数,是n&-n的封装)
• 某个变量a如果只有1,0两个值那么如果a^=1就可以做到 1变0,0变1 Acwing73.费解的开关
• 如果要对多个数进行0变1，1变0的操作那么可以对多个数的二进制进行求和然后异或 AcWing 116. 飞行员兄弟
• a&1可以用来判断a的奇偶性
• (x & (x-1)) == 0 用于判断x是否位2的整数次幂(因为x如果是偶数那么有且仅有最高位为1,那么x-1会使除最高位外全为1,进行与运算那么就全为0)
• n的二进制表示中第k位是多少(把第k位移到最后,看各位是几):n>>k&1

倍增

思想:所有的数都可以拆成二进制表示

快速幂

[AcWing 89. a^b](https://www.acwing.com/problem/content/91/
\begin{equation} a^b=a^{1b_1}a^{2b_2}a^{4b_3}……a^{(2^k)b_n}\end{equation}

\begin{equation}b_i=0或者1\end{equation}

64位乘法

AcWing 90. 64位整数乘法
\begin{equation}a*b=b个a相加\end{equation}

\begin{equation}a*1=a\end{equation}

\begin{equation}a*2=2a\end{equation}

\begin{equation}a*4=4a\end{equation}

\begin{equation}a*8=8a\end{equation}

\begin{equation}b=拆成二进制表示\end{equation}

因此

\begin{equation}a*b=a^{1b_1}+a^{2b_2}+a^{4b_3}+……+a^{(2^k)b_n}\end{equation}
\begin{equation}b_i=0或者1\end{equation}