位运算

进制

整数各种进制的字面量如下：

• 十进制数，没有前缀
• 二进制数，前缀是0b
• 八进制数，前缀是0o
• 十六进制数，前缀是0x

操作符

&  |  ^  ~
>> 右移 用符号位填充高位
<< 左移
>>> 右移，用0填充高位

& 与

1. 判断奇偶
2. 获取某个位上是0还是1 x & 1<<n
3. 判断二进制中1的个数

• 方法一：逐个数各个位 右移原数与1与运算，负数可能陷入死循环，可以右移1，与原数与运算
• 方法二：n&(n-1) 每次消除最低位的1，直到n为0

4. 判断一个数是不是2的整数次方 即问整数的2进制中是不是只有1个1

利用3中的方法二，n&(n-1)==0，则是2的整数次方

^ 异或

性质

满足 交换律 结合律
A^A=0 A^0=A

应用

1. 交换两个数 a=a^b; b=a^b; a=a^b;

需要注意的是，如果a和b指向同一个地址，那么将得到0值

2. 不使用判断语句求绝对值 a+(a>>31) ^ (a>>31)

a为正数 a>>31=0，a+(a>>31)=a, a^0=a

a为负数 a>>31=-1 a-1得到原码，原码取反得到正数

负数的二进制为补码 求补码的过程 正数原码 --> 求反得到反码 --> 再加1得到补码

3. 找出唯一成对的数

1-1000中，999个数都出现了一次，只有一个数出现了两次，找出这个数。

利用异或的性质，相同的数异或为0，0与任何数异或为任何数本身，将1-1000的数全部异或，再与目标数组异或，得到的数就是目标数。

4. 找出落单的数

   将所有数异或，得到的数就是落单的数。

5. 二进制数奇偶互换

  odd := a & 0x55555555  // 取所有奇数位
  even := a & 0xaaaaaaaa //取所有偶数位
odd<<1 ^ even>>1

运算优先级

指针最优，单目运算优于双目运算。如正负号。
先算术运算，后移位运算，最后位运算。

浮点数转二进制数

整数部分 除以2 有余数计1，无余数计0， 余数继续除以2 依次确定低位到高位
小数部分 乘以2，大于等于1 ，计1结果减去1；小于1计0；继续乘以2

不进位加法

1. 一个整数数列有只出现1次的数a,其他数均出现k次，求a
   k进制下，k个n相加，末位为0。
   解法是 将数字全部转为k进制，然后将相应位上的数相加对k取模，作为该位的值，得到的数就是只出现一次的数的k进制形式，再转成十进制即可。