leetcode day22 位运算

位运算咋这么老难

剑指 Offer 56 - I. 数组中数字出现的次数

借评论区大佬答案：nums = [1,2,10,4,1,4,3,3]

• a^a=0
• a^0=a
• a^b^c=a^c^b
• a&(-a)=最低位为1的二进制（从又到左）
• 所有的异或结果得到sum=2^10=8
• flag=-8&8=8
• 可分为两组，一组为与flag相与等于1的[10]，另一组为0的[1,2,4,1,4,3,3]
• 组内异或分别得到【10】【2】

public int[] singleNumbers(int[] nums) {int sum=0;//得到异或结果，即为不相同两个数的异或结果sumfor (int num : nums){sum ^= num;}// 得到sum的二进制1的最低位int flag = (-sum)∑int result[] = new int[2];//分成两个组进行异或，每组异或后的结果就是不相同两个数的其中之一for (int num : nums){if ((flag&num)==0)result[0] ^= num;elseresult[1] ^= num;}return result;}

 剑指 Offer 56 - II. 数组中数字出现的次数 II

思路：不用位运算的话挺简单，用位运算没啥思路

// 非位运算
public int singleNumber(int[] nums) {int result=0;Arrays.sort(nums);int i=0;while (i<nums.length-1){if (nums[i]!=nums[i+2]){result = nums[i];break;}i += 3;}result = nums[i];return result;}

位运算思路：如果一个数字出现3次，它的二进制每一位也出现的3次。如果把所有的出现三次的数字的二进制表示的每一位都分别加起来，那么每一位都能被3整除。 我们把数组中所有的数字的二进制表示的每一位都加起来。如果某一位能被3整除，那么这一位对只出现一次的那个数的这一肯定为0。如果某一位不能被3整除，那么只出现一次的那个数字的该位置一定为1.

public int singleNumber(int[] nums) {int [] k = new int[32];for(int i = 0 ; i < nums.length;i++){for(int j = 0 ; j <32;j++){k[j] += (nums[i]>>j & 1) == 1 ? 1 : 0;}}int res = 0;for(int i = 31;i>=0;i--){res = res << 1;if(k[i]%3 == 1){res = (res | 1);}}return res;}