位运算

常用操作：

• $n*2^k$ :n<<k

• $n/2^k$:n>>k

• $2^k$:1<<k

• $n$在二进制下最后一位的数（奇偶）:n&1

• $n$在二进制下的第$k$位：

  先把第$k$位移到末尾:n>>k

  再判断当前位的数值:n&1

  合起来:n>>k&1

• $lowbit$ :

  $lowbit(x)$：返回$x$的最后一位$1$

  实现：x&-x

  原理：$-x=\sim x+1$ （$\textasciitilde$表示取反）, 设$x$的第$k$位是$1$,则$\sim x$的$1\thicksim k-1$位都是$1$,第$k$位是$0$,加$1$后产生进位，使第$1\thicksim k-1$都变为$0$,第$k$位是$1$。因为加$1$后不会影响$k$位以上，所以$k$位以上都与原数相反,进行$&$操作后都为$0$,第$1\thicksim k-1$也为$0$,所以只有第$k$位是$1$。

  例：$x=100=(1100100)_2$

  ​ $\sim x=(0011011)_2$

  ​ $-x=\sim x+1=(0011100)_2$

  ​ $x&-x=(0000100)_2$

  例题：求$n$个数$x$的二进制中$1$的个数

  分析：当$x$不为零时，每次减去$x$的最后一位$1$，统计次数

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  #include<bits/stdc++.h> using namespace std; int n; int lowbit(int x){ return x&-x; } int main(){ cin >> n; while(n--){ int x,ans=0; cin >> x; while(x){ ans++; x-=lowbit(x); } cout << ans << ' '; } return 0; }

  应用：树状数组

• 原码、反码、补码

  反码$=$原码取反

  补码$=$反码$+1$

  例：$x=100$

  原码：00...001100100

  反码：11...110011011

  补码：11...110011100