算法-位操作

Bitwise AND of Numbers Range

求m ~ n之间所有数字的与。

思路：一开始就是暴力与。但这样超时了。

参考资料[LeetCode] Bitwise AND of Numbers Range 数字范围位相与

我们先从题目中给的例子来分析，[5, 7]里共有三个数字，分别写出它们的二进制为：

101　　110　　111

相与后的结果为100，仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，如果上面那个例子不太明显，我们再来看一个范围[26, 30]，它们的二进制如下：

11010　　11011　　11100　　11101　　11110

发现了规律后，我们只要写代码找到左边公共的部分即可。

直接平移m和n，每次向右移一位，直到m和n相等，记录下所有平移的次数i，然后再把m左移i位即为最终结果，代码如下：

public int rangeBitwiseAnd(int m, int n) {
       // 统计m和n的高位相等的个数
       int counter = 0;
       while (m != n){
           m = m >> 1;
           n = n >> 1;
           ++counter;
       }
       // 将m左移counter次就是结果
       return m << counter;
   }

Single Number

给一个数组，数组中只有一个元素是单个出现的，其它都是成对出现。找到这个元素。

思路：由于x ^ 0 = x, x ^ x = 0 , 因此 x ^ x ^ y ^ z ^ z = y

public int singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }

Reverse Bits

将无符号整数按位反转。

public int reverseBits(int n) {
        int result = 0;
        for(int i = 0; i < 32; ++i) { // 注意：这里不可以用 n > 0的判断！因为是无符号的！
            result <<= 1;
            result += (n & 1); // n & 1 == n % 2
            n >>= 1;
        }
        return result;
    }

Number of 1 Bits

求一个无符号整数的1bit的个数

public int hammingWeight(int n) {
        int counter = 0;
        for(int i = 0; i < 32; ++i){
            counter += (n & 1);
            n >>= 1;
        }
        return counter;
    }

Maximum Product of Word Lengths

给一些str。求两个没有共有字母的word的长度乘积的最大值。

public int maxProduct(String[] words) {
    int[] bitCount = new int[words.length];
    for(int i = 0; i < words.length; ++i){
        for(char c : words[i].toCharArray()){
            bitCount[i] |= (1 << (c-'a')); // 将第c-'a'位 置为1
        }
    }
    int max = 0;
    for(int i = 0; i < words.length; ++i){
        for(int j = i + 1; j < words.length; ++j){
            if((bitCount[i] & bitCount[j]) == 0){ // 如果word[i]和word[j]的与为0，则说明没有共有的字母
                max = Math.max(words[i].length() * words[j].length(), max);
            }
        }
    }
    return max;
}

Integer Replacement

输入n,给定以下操作：

如果n是偶数，则将n替换为n/2
如果n是奇数，则将n替换为n+1或者n-1

求一个n变为1的最少操作次数

思路一，递归

private int helper(long n){
        if(n == 1) return 0;
        if(n % 2 == 0) return  1 + helper(n/2);
        else return 2 + Math.min(helper((n+1)/2), helper((n-1)/2));
    }
    public int integerReplacement(int n) {
        return helper(n);
    }

(话说这个递归改成记忆化搜索之后居然过不了)

思路二，位操作

首先，对于任意偶数，只有一个选择，即除以2，总的步数增加1。然后，对于任意奇数，无论加一或者减一，得到的必然是偶数，依然还要要除以2，步数增加2。所以归结的问题是，奇数到底是加一还是需要减一呢？

举一个简单的例子，数字5，当5+1=6时，明显不如5-1=4快，因为6除以2后又是一个奇数3，对比5-1得到的4，需要额外的两步变为4 (5->6->3->4 vs 5->4)，或者多一步数变为2 (5->6->3->2 vs 5->4->2)。其实上，数字尽可能为偶数，是最快的。

如上所述，奇数无论加减1，如果得到的数能被4整除（偶数的2倍），那么就是快的。对于任意奇数，可以写成4n+1或者4n+3的形式。适当加一或者减一，总有可能被4整除，所以实际中只要测试其中一种运算即可。这里面要考虑一个特例：3变4，因为3->2->1结束。

public int integerReplacement(int n) {
        if(n == 3) return 2;
        int total = 0;
        while (n != 1){ // n可能为负（溢出了），因此不可以用n > 1
            if(n % 2 == 0){
                n >>>= 1; // >>> 表示无符号右移
            }else if(n == 3 || (n + 1) % 4 != 0){
                --n;
            }else{
                ++n;
            }
            ++total;
        }
        return total;
    }

改进版：

public int integerReplacement(int n) {
        if(n == 3) return 2;
        int total = 0;
        while (n != 1){ // n可能为负（溢出了），因此不可以用n > 1
            if(n % 2 == 0){
                n >>>= 1; // >>> 表示无符号右移
            }else if(n == 3 || ((n + 1) & 1) == 1 || (((n + 1) >>> 1) & 1) == 1){
                // ((n + 1) & 1) == 1 表示n+1 这个数字的二进制最后一位是1，因此它一定不是4的倍数
                // (((n + 1) >> 1) & 1) == 1 表示n+1这个数字的二进制倒数第二位是1，因此它一定不是4的倍数
                --n;
            }else{
                ++n;
            }
            ++total;
        }
        return total;
    }

Hamming Distance

给两个整数，计算两个整数的二进制汉明距离

public int hammingDistance(int x, int y) {
    int bit = 1;
    int dist = 0;
    // 每次比较最低位的异或，如果异或为1，则距离+1；如果异或为0，则距离不变
    
    // 两个都不为0时
    while(x > 0 && y > 0){
        dist += ((bit & x)^(bit & y));
        x = x >> 1;
        y = y >> 1;
    }
    // 挑出一个还没为0的数字继续计算
    if(y > 0) x = y;
    while(x > 0){
        dist += (bit & x);
        x = x >> 1;
    }
    return dist;
}

另一种方式：

1
2
3

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

甲乙小朋友的房子