位运算第一弹

1.基础位运算

191 338 461

<<   左移

&按位与      有0就是0

>>   右移

||按位或      有1就是1

~     按位取反

^按位异或  

相同为0，不同为1，无进位相加（正常1+1是前进，但是他不进行进位)

位运算的优先级，能加括号，就加括号，这样最不容易出错

这个取反，相当于是个简单操作，就是开始把所有都是0，然后把1放在x的位置，然后，再一个取反。

位图的思想

异或运算的运算律

a^0=a

a^a=0

a^b^c=a^(b^c)

偶数全部会被干掉，只剩一个奇数

引入题目

力扣136.只出现一次的数字

这题的审题，首先看他是只有一个数字是单独一个的，其他的数字都是两个

异或的本质就是相加的时候，不去进位，相当于消消乐，偶数就消去

class Solution {
    public int singleNumber(int[] nums) {
      int ret=0;
      for(int x:nums){
          ret=ret^x;
      }
      return ret;
    }
}

力扣260.只出现一次的数字III

     s = 101100
    ~s = 010011
(~s)+1 = 010100 // 根据补码的定义，这就是 -s   效果：s 的最右侧的1（也叫最低位）左侧取反，右侧不变
s & -s = 000100 // lowbit
    
链接：https://leetcode.cn/problems/single-number-iii/solutions/2484352/tu-jie-yi-zhang-tu-miao-dong-zhuan-huan-np9d2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

首先先导入知识

这个题解说的很细，很吊

首先：他不可能最后异或的结果全部是0，因为有两个不同的数字，所以，最后肯定有一个数是1，那么就肯定是有一个是0，有一个是1。

那么假如极端点，全部都是1，比如1111

例如0000^1111其他的我们不去关注，因为全部都会出现两个。

所以我们都使用这个保留最后一个1的方式。

然后我们进行什么操作呢?

->把最后那个为1的位，我们进行分组，因为最后是1，所以那两个单独的肯定是一个0，一个1，其余的我们不用操心，我总是担心什么出现5个1，3个0，但是这么想没有必要，到最后还是

分组成0和1，最后我们用这个&来分组，把那个位置为0的和为1的区分开来，哪怕只有一个是0，有999个1，那也是区分开来，然后有一个是单独的。

class Solution {
    public int[] singleNumber(int[] nums) {
    int[]ret=new int[2];
    Arrays.sort(nums);
    int m=0;
    int count=0;
   for(int x:nums){
       m=m^x;
   }
   int lowbit=m&-m;
   for(int x:nums){
       ret[(lowbit & x)== 0?0:1]^=x;
   }
    return ret;
    }
}