一、用位运算实现普通运算的效果

  • a+b

    1. // int a,b;  求a+b
    2. while(b!=0){
    3.   int carry=(a&b)<<1; //进位
    4. a=a^b;    //原位结果
    5. b=carry;
    6. }
    7. return a;

  • a/2=a>>1

  • a%2=a&1
  • 取第i位 ：a&(1<<i)
  • 将位数最靠后的1变成0：a&(a-1)。应用：数1的个数
  • 异或的性质 ^
    • a^a=0，0^y=y
    • 交换律
    • 应用：求0-n中遗漏的数字。使所有数字异或的结果再依次与0-n异或

二、一个数组中只有一个数只出现一次，其他数都出现N次，求那个出现一次的数

如果N为偶数，所有数全部异或，得到的结果就是那个出现一次的数。因为相同的数异或偶数次后一定为0，0和a异或得到a。
如果N为奇数，则每一个数用二进制表示，出现重复的数其第i位叠加的结果对于重复次数取余一定是0，如果所有数第i位叠加后取余结果为1，说明单独出现一次的数在该位上是1，否则是0.