博客

一. 位运算

• Java int 类型可以直接进行位运算，位运算进行时是换算成二进制运算的，运算完成后的结果也是十进制的 int 类型；
• n & (n-1) 可以去除 n 中最低位的 1；如 0100 & 0011 = 0000
• n & (-n) 可以得到 n 中最低位的 1；（注意负数在计算机中是以补码的形式出现），如 0100 & 1100 = 0100。

1. 基础问题

例题461，汉明距离。两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

• 汉明距离是两个二进制数异或

    public int hammingDistance(int x, int y) {
        //int类型可以直接异或，异或完以后还是int类型（十进制）
        int diff = x ^ y;
        //计算diff有几个1
        int res = 0;
        while(diff > 0) {
            //和1相与，判断最后一位是0还是1
            res += diff & 1;
            //右移去除最低位
            diff = diff >> 1;
        }
        return res;
    }

还可直接利用性质——n & (n-1) 可以去除 n 中最低位的 1——进行计算：

public int hammingDistance(int x, int y) {
        //int类型可以直接异或，异或完以后还是int类型（十进制）
        int diff = x ^ y;
        int res = 0;
        while(diff > 0) {
            res ++;
            diff = diff & (diff-1);
        }
        return res;
    }

例题190，颠倒二进制位。颠倒给定的 32 位无符号整数的二进制位。注意数据溢出问题。

• 可以仿照十进制代码翻转的题目进行二进制翻转。但是要考虑溢出的问题，因此采用位运算。
• 另外题目明确说明了是32位数，因此需要循环32次。

public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res = res << 1; //右移一位
            res += n & 1; //取n最后一位
            n = n >> 1; //n左移一位
        }
        return res;
    }

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

• 使用异或找出只出现一次的元素。利用 x ^ 0 = x，x ^ x = 0 的性质，遍历数组，将所有数进行异或，最后所有相同的数异或为0，0与只出现一次的那个元素异或等于那个元素。
• 说明异或满足交换律，不考虑元素出现的顺序。

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

例题268，丢失的数字。给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

• 只出现一次的数字和丢失的数字都是异或的经典问题。将[0, n] 中所有的数字都异或一次，再与nums数组中的数字都异或一次，则丢失的数字只出现一次，其余数字出现两次，异或之后的结果即是丢失的数字。
• 另一种解法是计算nums的累加和，再利用公式（首项+尾项）* 项数 / 2 减累加和得到结果。

public int missingNumber(int[] nums) {
        int res = 0;
        int n = nums.length;
        for (int i = 0; i <= n; i++) {
            res = res ^ i;
        }
        for (int num : nums) {
            res = res ^ num;
        }
        return res;
    }

例题 260。只出现一次的数字2。给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

• 这道题只出现一次的元素有两个，可以想着怎么将其转化为只含一个的题。
• 先将所有数全部异或一遍，取得数的其中为1的一位，在该位两个只出现一次的数必然一个是1，一个是0。其他出现两次的数在该位无论是1还是0都没关系。
• 根据此特性将数组分为两组，则每一组中都只含一个出现一次的元素。再分别进行异或。

public int[] singleNumber(int[] nums) {
        //先全部异或一遍
        int ans = 0;
        for(int num : nums) {
            ans = ans ^ num; 
        }
        //取ans的其中为1的一位，在该位两个只出现一次的数必然一个是1，一个是0
        //其他出现两次的数在该位无论是1还是0都没关系
        //根据此特性将数组分为两组，则每一组中都只含一个出现一次的元素
        ans = ans & (-ans); //取最低位为1的
        int[] res = new int[2];
        for (int num : nums) {
            //当前数在该位是1
            if ((ans & num) == ans) {
                res[0] = res[0] ^ num;
            } else {
                res[1] = res[1] ^ num;
            }
        }
        return res;
    }

2. 二进制特性

例题318，最大单词长度乘积。给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

• 这道题最大的问题是如何快速判断两个单词是否含有相同的字母。
• 可以为每个单词创建一个长度为26的二进制数字，用1表示字母出现，0表示字母未出现。两个单词如果含有相同的字母，则二进制数字相与为0。

public int maxProduct(String[] words) {
        int[] arr = new int[words.length]; 
        for (int i = 0; i < words.length; i++) {
            char[] word = words[i].toCharArray();
            int r = 0;
            for (char w : word) {
                int t = w - 'a';
                r  = r | 1 << t; // 将 1 右移 t 位，然后与 t 或
            }
            arr[i] = r;
        }
        int res = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = i+1; j < words.length; j++) {
                if ((arr[i] & arr[j]) == 0) {
                    res = words[i].length() * words[j].length() > res ? words[i].length() * words[j].length() : res;
                }
            }
        }
        return res;
    }

例题 338，比特位计数。给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

• 利用 n&(n-1) 可以去除最后一位1的性质计数。

public int[] countBits(int n) {
        int[] ret = new int[n+1];
        int count = 0;
        int tmp = 0;
        for (int i = 0; i <= n; i++) {
            count = 0;
            tmp = i;
            while (tmp != 0) {
                count ++;
                tmp = tmp & (tmp-1);
            }
            ret[i] = count;
        }
        return ret;
    }

• 动态规划与位运算结合。如果当前数最后一位是1，则1的个数等于它前一个数1的个数+1；如果等于0，则1的个数等于该数右移1位后得到的数的1的个数。

public int[] countBits(int n) {
        int[] dp = new int[n+1];
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            //如果当前数最后一位是1
            if ( (i & 1) == 1) {
                dp[i] = dp[i-1] + 1;
            } else {
                dp[i] = dp[i >> 1];
            }
        }
        return dp;
    }

• 还可以将动态规划与 n&(n-1) 的性质结合一下：i & (i-1) 比 i 少一个1，且 i > i & (i-1)

public int[] countBits(int n) {
        int[] dp = new int[n+1];
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i & (i-1)] + 1;
        }
        return dp;
    }

例题 693，交替位二进制数。给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

• 自己写的笨方法，while循环不断获取最后一位，判断最后一位是否不同。

public boolean hasAlternatingBits(int n) {
        int t1 = 0;
        int t2 = 0;
        while (n != 0) {
            t1 = n & 1;
            n = n >> 1;
            t2 = n & 1;
            if ((t1 ^ t2) != 1) {
                return false;
            }
        }
        return true;
    }

• 看题解获得的解法，超帅！如果某数是 0 1 交替出现，那么该数右移一位将得到 1 0 交替出现的数，两者异或必得到全1的数。全1 的数与该数+1 的数相与将得到全零的数。

public boolean hasAlternatingBits(int n) {
        int m = n ^ (n >> 1); //如果是交替出现将得到全1的数
        return (m & (m + 1)) == 0;
    }

例题 476，数字的补数。对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。例如，整数 5 的二进制表示是 “101” ，取反后得到 “010” ，再转回十进制表示得到补数 2 。给你一个整数 num ，输出它的补数。

• 关键是如何得到十进制数对应的二进制数的位数，即最高位1是第几位。
• 可不断循环得到位数，再与高一位的数减1（全一）异或，则得到相反数。

public int findComplement(int num) {
        int n = num;
        int s = 1;
        while (n > 0) {
            n = n >> 1;
            s = s * 2;
        }
        return num ^ (s -1);
    }