位运算

剑指 Offer 15. 二进制中1的个数

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

思路：
位运算。和 1 进行“与”操作，然后将 n 右移一位，直到 n 等于 0。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0) {
            if((n&1) == 1) res++;
            n = n>>>1;
        }
        return res;
    }
}

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

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

思路1：
栈。
执行用时：17 ms, 在所有 Java 提交中击败了7.23%的用户
内存消耗：41.8 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int[] singleNumbers(int[] nums) {
        int[] res = new int[2];
        Arrays.sort(nums);
        Stack<Integer> stack = new Stack<>();
        for (int num : nums) {
            if (stack.isEmpty() || stack.peek() != num) {
                stack.push(num);
            } else if (stack.peek() == num) {
                stack.pop();
            }
        }
        res[0] = stack.pop();
        res[1] = stack.pop();
        return res;
    }
}

思路2：
分组异或。
执行用时：2 ms, 在所有 Java 提交中击败了97.28%的用户
内存消耗：41.4 MB, 在所有 Java 提交中击败了60.78%的用户

class Solution {
    public int[] singleNumbers(int[] nums) {
        int sum = 0;
        int[] res = new int[2];
        for(int num : nums){
            sum ^= num;
        }
        int lowbit = sum & (-sum);
        for(int num : nums){
            if((num & lowbit) == 0){
                res[0] ^= num;
            }else{
                res[1] ^= num;
            }
        }
        return res;
    }
}

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

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

思路：
哈希表。
执行用时：16 ms, 在所有 Java 提交中击败了47.02%的用户
内存消耗：41 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num,0)+1);
        }
        for (int k : map.keySet()) {
            if (map.get(k) == 1) return k;
        }
        return -1;
    }
}

思路2：
异或。

class Solution {
    public int singleNumber(int[] nums) {
        int a = 0;
        int b = 0;
        for(int num : nums) {
            a = (a ^ num) & ~b;
            b = (b ^ num) & ~a;
        }
        return a;
    }
}

剑指 Offer 65. 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

思路：
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.2 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int add(int a, int b) {
        int sum = a ^ b;
        int carry = (a & b) << 1;
        while(carry != 0) {
            int temp = sum;
            sum = sum ^ carry;
            carry = (temp & carry) << 1;
        }
        return sum;
    }
}