二进制与位运算

位运算与乘除法的换算

• 说明：
  （1）位运算符中除 ~ 外，均为二目运算符，即要求出侧各有一个运算量。
  （2）运算早只能是整型或字符型的数据，不能为实型数据。
• 使用位移运算可以提高因乘除运算带来的效率的问题，它的缺点是存在精度损失且不直观。
• 使用移位运算来避免乘法运算是一种常用技巧，不过乘数必须都是正整数，而且必须至少有一个是 2 的 n 次方，例如：2，4，8，16，32……移位运算的特点是速度快，而乘法运算速度较慢，把乘法运算转化为移位运算可以稍微提高程序运行效率。
• 例题1：

  //乘法
  12 * 2 = 12 << 1
  12 * 4 = 12 << 2
  12 * 8 = 12 << 3
  12 * 16 = 12 << 4
  12 * 32 = 12 << 5
  12 * 64 = 12 << 6
  12 * 128 = 12 << 7
  12 * 256 = 12 << 8
  //除法
  12 / 2 = 12 >> 1
  12 / 4 = 12 >> 2
  12 / 8 = 12 >> 3
  12 / 16 = 12 >> 4
  12 / 32 = 12 >> 5
  12 / 64 = 12 >> 6
  12 / 128 = 12 >> 7
  12 / 256 = 12 >> 8
  //其它
  num *= 32;  
  //等同于 
  num <<= 5; 
  /* 2 的 5 次方等于 32 */ 
  //如果乘数不是 2 的 n 次方，我们可以把乘数分解成几个 2 的 n 次方的和：
   num *= 20;
  //等于
   num *= (16 + 4);
  //等于
   num = num * 16 + num * 4;
  //等于
  num = (num << 4) + (num << 2);

二进制

• 原码:指一个二进制数左边加上符号位后所得到的码，且当二进制数大于0时，符号位为0；二进制数小于0时，符号位为1；二进制数等于0时，符号位可以为0或1
• 反码：正数的反码与其原码相同；负数的反码是对其原码逐位取反，但符号位除外。
• 补码：正数的补码与原码相同，负数的补码是其对应正数二进制所有位取反后加1。
• 在计算机中通常使用补码进行储存。
• 二进制的最末位为0表示该数是偶数，最末位为1表示该数为奇数

位运算

“~”运算

又称取反运算，就是对一个二进制数按位取反。
对于 int 来说，~x = −x−1

“&”运算

• “&”运算，即“and” 运算，也是一种逻辑运算符，对于二进制运算来说，“&”运算的意义是对于两个二进制数的每一位，除了11得1，其他均为0
• 可以用 & 运算判断一个数是奇数还是偶数，当 x 为奇数时， x 二进制下的第 0 位一定是 1 ，否则为 0 。我们让x & 1，就可以知道 x 的奇偶性了。
  • &运算通常用于二进制取位操作，例如一个数 &1的结果就是取二进制的最末位。所以可以用来判断奇偶性
  • 举个栗子：10101(21) & 11100(28) = 10100{20}

• 如果参加 & 是负数（-3 & -5），则以补码形式表示为二进制数。然后按位进行 与 运算。

• x & (x - 1)用于消去x二进制最后一位的1

  x = 1100            00|0100|1100
  x - 1 = 1011        00|0100|1011
  x & (x - 1) = 1000  00|0100|1000

“|” 运算

• 即 “or” 运算，也是一种逻辑运算符，对于二进制运算来说，“|” 运算的意义是对于两个二进制数的每一位，除了00得0，其它都是1
  • 举个栗子：10101(21) | 11100(28) = 11101(29)
• 通过与运算和或运算的栗子可以观察到一下规律：x & y<=x和x | y>=x

“^”运算

• “^”运算，又称“xor”运算，异或运算。定义是对于两个二进制数的每一位，相同为0，不同为1
  • 举个栗子：10101(21) ^ 11100(28) = 1001(9)
• 对于一个形如2∗n 的数 x， x ^ 1=x+1,而对于一个形如 2∗n+1的数x，x ^ 1=x−1
• 异或运算的妙用：
  • 0^0=0,0^1=1 可理解为：0异或任何数，其结果=任何数
  • 1^0=1,1^1=0 可理解为： 1异或任何数，其结果=任何数取反
  • 任何数异或自己，等于把自己置0
  • 异或运算符的特点是：数a两次异或同一个数b（a=a^b^b）仍然为原值a.
  • 如果 x ^ y=z 那么 y ^ z=x， x ^ z=y
  • a xor c == b xor c 则 a == b
  • a ^ b = b ^ a
  • a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
  • d = a ^ b ^ c 可以推出 a = d ^ b ^ c.
  • a ^ b ^ a = b.
  • (a xor b） xor b = a;
  • 由于xor满足交换律，所以上述特性这样表述也是对的：
    • (b xor a) xor b = a;
    • b xor (a xor b) = a;

      交换2个数

• 不借助中间变量，交换两个数有以下方法👇

• 1. 相互加减

  a = a + b;         //但是加法可能导致溢出
  b = a - b;       //x和y同号的情况下容易溢出
  a = a - b;
  
  x=x-y;    //x和y异号的情况下容易溢出
  y=x+y;
  x=y-x;

• 2.异或运算

  a = a^b;
  b = a^b;
  a = a^b;
  //可简写为如下
  b ^= a ^= b ^= a;

• 这东西理论上能比正常的交换优一点，当然还是用 swap 吧，毕竟人家什么都能换，这个只能换整数。

  找出2n+1个数中不成对的数

• 给出n个数，其中有且仅有一个出现了奇数次，其余的都出现了偶数次。用线性时间常数空间找出这个出现奇数次的数原
  -
  

  lowbit运算

  快速判断奇偶性

• 上面有

  在状压情况下的操作

  快速幂

  位运算的优先级

• 位运算的优先级，大致按下面排序
  • 加减运算 > 移位运算 > 比较大小运算 > 与运算 > 异或运算 > 或运算