算法-位运算（Java实现）

位运算的一些技巧

位运算面试题常用技巧
万字长文！位运算面试看这篇就够了！

• x&(-x)：只保留二进制下最后出现的1的位置，其余位置置0
• x&(x-1)：把x的最后一位的1变为0之后的结果。

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

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

思路：

思考一个简单的场景，如果数组中只有一个出现一次的数字，那么我们直接所有全部数字，异或即可。对于两个操作数的每一位，相同结果为 0，不同结果为 1。那么在计算过程中，成对出现的数字的所有位会两两抵消为 0，最终得到的结果就是那个出现了一次的数字。

现在最主要的就是：有两个出现一次的数字，其实就是：以这两个数字的异或结果的某一位二进制位，作为分组位去进行区分即可，具体见代码

思路见：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/xue-sheng-wu-de-nu-peng-you-du-neng-kan-jucmy/

class Solution {
    public int[] singleNumber(int[] nums) {
        int temp = 0;
        //求出异或值
        for (int x : nums) {
            temp ^= x;
        }
        //保留最右边的一个 1
        int group = temp & (-temp);
        System.out.println(group);
        int[] arr = new int[2];
        for (int y : nums) { 
            //分组位为0的组，组内异或
            if ((group & y) == 0) {
                arr[0] ^= y;
            //分组位为 1 的组，组内异或   
            } else {
                arr[1] ^= y;
            }
        }
        return arr;
    }
}

• 时间：O(n)
• 空间：O(1)

191. 位1的个数

https://leetcode-cn.com/problems/number-of-1-bits/

思路1：

判断32次，每次判断二进制的最后一位数字是不是1即可。（通过 和1做与运算 来判断）

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        if (n == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < 32; i++) {
            // 注意这里：如果写为 == 1 的话，是不对的，
            // 因为判断的不一定是最后一位，而是某一位
            if ((n & 1) != 0) {
                count++;
            }
            n >>= 1;
        }
        return count;
    }
}

思路2：

x&(x-1) 是把x的最后一位的1变为0之后的结果。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        if (n == 0) {
            return 0;
        }
        int count = 0;
        while (n != 0) {
            // 剔除最后一位 0
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

231. 2 的幂 与 338. 比特位计数

https://leetcode-cn.com/problems/power-of-two/

https://leetcode-cn.com/problems/counting-bits/

//1. 2 的幂
class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        // 所有的2的幂都是 0000000x000000，所以剔除最后一位后都是等于0
        return (n & (n - 1)) == 0;
    }
}
//2. 比特位计数(动态规划的意味)
class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        result[0] = 0;
        // 注意下标别越界了
        for (int i = 1; i <= n; i++) {
            // x 的二进制数量 就是 x&x-1 的二进制数量+1
            result[i] = result[i & i - 1] + 1;
        }
        return result;
    }
}