算法–位运算

概念

符号 描述 运算规则
& 与 两个位都为1时，结果才为1
\ 或 两个位都为0时，结果才为0
^ 异或 两个位相同则为0，相异为1
~ 取反 0变1，1变0
<< 左移 各二进位全部左移若干位，高位丢弃，低位补0
>> 右移 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

异或操作的一些特点

1
2
3
4
5
6
X^0=X
X^1s = ~X  //1s = ~0(1s表全1的数)
X^(~X) =1s
X^X = 0 //important
a^b =c=>a^c=b,b^c=a //swap 
a^b^c = a^(b^c)=(a^b)^c//结合律

实战中常用位运算操作

  • X&1==1 OR ==0 =>判断奇偶（x%2==1）
  • x=x&(x-1)=>清零最低位的1
  • X&-X=>得到最低位的1
  • 将x最右边的n位清零-x&（~0<<n）
  • 获取x的第n位值（0或者1）-（x>>n）&1
  • 获取x的第n位的幂值-x&（1<<（n-1））
  • 仅将第n位置为1-x |（1<<n）
  • 仅将第n位置为0-x &（~（1<<n））
  • 将x最高位至第n位（含)清零-x &（（1<<n）-1）
  • 将第n位至第0位（含）清零-x &（~（（1<<（n+1））-1））