位运算-191. 位1的个数- 136. 只出现一次的数字

191. 位1的个数 已解答 简单 相关标签 相关企业 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

示例 1：

输入：n = 11 输出：3 解释：输入的二进制串 1011 中，共有 3 个设置位。 示例 2：

输入：n = 128 输出：1 解释：输入的二进制串 10000000 中，共有 1 个设置位。 示例 3：

输入：n = 2147483645 输出：30 解释：输入的二进制串 11111111111111111111111111111101
中，共有 30 个设置位。

思路：
看清题目因为无符号，所以我们在右移动时用无符号右移。
这个就是先把数和1做&运算（&符号是遇见0变0，所以我们相当于是计算数的最后一位和1的比较，如果是0那么结果为0，如果是1结果为1） ，然后相加记录个数，遍历完一次之后，需要将数无符号右边移动1位，直至循环结束。

class Solution {
    public int hammingWeight(int n) {
        int index=0;
        for(int i=0;i<=32;i++){
          index +=  n & 1;
          n >>>=1;
        }

        return index;   


    }
}

136. 只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1] 输出：1 示例 2 ：

输入：nums = [4,1,2,1,2] 输出：4 示例 3 ：

输入：nums = [1] 输出：1

提示：

1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104 除了某个元素只出现一次以外，其余每个元素均出现两次。

看清题目：我们这里使用异或运算，至于为什么，看下图我的解释。

class Solution {
    public int singleNumber(int[] nums) {
    
    int s=nums[0];
    for(int i=1;i<nums.length;i++){
        s = s ^ nums[i];
    }
        return s;
    }
}

一开始我的想法是map来做，没看清题目要求空间复杂度是只使用常量额外空间。
我下面的代码空间复杂度是O（n）

public class Main {
    public static void main(String[] args) {
        int [] nums ={1,2,3,1,2};
        System.out.println(han(nums));

    }
    public  static  int han (int[] nums){
        HashMap<Integer,Integer> map=new HashMap<>();

        for(int i=0;i<nums.length;i++){
            int count=1;
            if(map.containsKey(nums[i])){
                count++;
            }
            map.put(nums[i],count);
        }

   for(int i=0;i<nums.length;i++){
       if(map.get(nums[i])==1){
           return  nums[i];
       }
   }
        return -1;
    }

    }