算法训练——位运算（LeetCodeHOT100）

摘要

算法有关于位运算算法。

461. 汉明距离

思路及算法：大多数编程语言都内置了计算二进制表达中1的数量的函数。在工程中，我们应该直接使用内置函数。

 public int hammingDistance(int x, int y) {
        return Integer.bitCount(x^y);
    }

复杂度分析

• 时间复杂度：O(1)。不同语言的实现方法不一，我们可以近似认为其时间复杂度为 O(1)。

• 空间复杂度：O(1)。

移位实现位计数

具体地，记 s=x⊕y，我们可以不断地检查 s 的最低位，如果最低位为 1，那么令计数器加一，然后我们令 s整体右移一位，这样 s的最低位将被舍去，原本的次低位就变成了新的最低位。我们重复这个过程直到 s=0为止。这样计数器中就累计了 s 的二进制表示中 1 的数量。

public int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            ret += s & 1;
            s >>= 1;
        }
        return ret;
    }

在方法二中，对于 s=(10001100)2的情况，我们需要循环右移 8次才能得到答案。而实际上如果我们可以跳过两个 1之间的 0，直接对 1 进行计数，那么就只需要循环 3次即。我们可以使用 Brian Kernighan 算法进行优化，具体地，该算法可以被描述为这样一个结论：记 f(x) 表示 x 和 x-1 进行与运算所得的结果即 f(x)=x & (x−1)，那么 f(x) 恰为 x 删去其二进制表示中最右侧的 1的结果。

基于该算法，当我们计算出 s=x⊕y，只需要不断让 s=f(s)，直到s=0 即可。这样每循环一次，s 都会删去其二进制表示中最右侧的 1，最终循环的次数即为 s 的二进制表示中 1的数量。

class Solution {
    public int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            s &= s - 1;
            ret++;
        }
        return ret;
    }
}

136. 只出现一次的数字

    public int singleNumber(int[] nums) {
        int res=0;
        for (int i:nums){
            res=res^i;
        }
        return res;
    }

338. 比特位计数

Brian Kernighan 算法

package 位运算;

import org.junit.Test;

public class countBits338 {

    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        int index = 0;
        for (int i = 0; i