02 二进制

二进制的位运算主要有 6 种：非，与，或，异或，左移和右移。

2.1 二进制的 6 种运算

非运算

非运算对整数的二进制按位取反，0 取反得 1, 1 取反得 0，下面对 8 为整数进行非运算：

~ 00001010 = 11110101

~ 10001010 = 01110101

与，或和异或的运算规律如下表：

运算符	计算1	计算2	计算3	计算4
与 ( & )	0 & 0 = 0	1 & 0 = 0	0 & 1 = 0	1 & 1 = 1
或 ( | )	0 | 0 = 0	1 | 0 = 1	0 | 1 = 1	1 | 1 = 1
异或 （ ^ ）	0 ^ 0 = 0	1 ^ 0 = 1	0 ^ 1 = 1	1 ^ 1 = 1

左移运算符

左移运算符 m << n 表示把 m 左移 n 位。如果左移 n 位，那么最左边的 n 位将被丢弃，同时在最右边补上 n 个 0。具体示例如下：

00001010 << 2 = 00101000

10001010 << 3 = 01010000

右移运算符

右移运算符 m >> n 表示把 m 右移 n 位。如果右移 n 位，那么最右边的 n 位将被丢弃，但右移时处理最左边位的情形比较复杂。如果数字是一个无符号数值，则用 0 填补最左边的 n 位。如果数字是一个有符号数值，则用数字的符号位填补最左边的 n 位。也就是说，如果数字原先是一个正数，则右移之后在最左边补 n 个 0；如果数字原先是一个负数，则右移之后在最左边补 n 个 1。 值（Java中的byte型整数）进行右移的例子：

00001010 >> 2 = 00000010

10001010 >> 3 = 11110001

Java 中增加了一种无符号右移位操作符 “ >>>”。无论是对正数还是负数进行无符号右移操作，都将在最左边插入 0。下面是对 Java 中 byte 型整数进行无符号右移操作的例子：

00001010 >>> 2=00000010

10001010 >>> 3=00010001

其他编程语言（如C或C++）中没有无符号右移位操作符。

题目 2: 二进制加法

输入两个表示二进制的字符串，请计算它们的和，并以二进制字符串的形式输出。例如，输入的二进制字符串分别是"11"和"10"，则输出"101"。

分析

从右向左依次计算每一位的数字，如果大于等于2，进一位，直到计算完所有的字符。

==注意 java 中，计算 char 的整数是 字符 - '0' 比如： char 的字符 a，则对应的整数为 a - '0'==

代码

package com.zj.offer.code;

import java.util.Objects;

/**
 * 作者: zhoujun134
 * 时间: 2023/12/3 22:34
 */
public class Test02 {
    public static void main(String[] args) {
        System.out.println(addBinary("11", "10"));
    }

    public static String addBinary(String str1, String str2) {
        int i = str1.length() - 1;
        int j = str2.length() - 1;
        int carry = 0;
        StringBuilder result = new StringBuilder();
        while (i >= 0 || j >= 0) {
            int digitA = i >= 0 ? str1.charAt(i--) - '0' : 0;
            int digitB = j >= 0 ? str2.charAt(j--) - '0' : 0;
            int sum = digitA + digitB + carry;
            carry = sum >= 2 ? 1 : 0;
            sum = sum >= 2 ? sum - 2 : sum;
            System.out.println(sum);
            result.append(sum);
        }
        if (carry == 1) {
            result.append(1);
        }
        return result.reverse().toString();
    }
}

题目 3: 前 n 个数字二进制形式中 1 的个数

题目：输入一个非负数 n，请计算 0 到 n 之间每个数字的二进制形式中 1 的个数，并输出一个数组。例如，输入的 n 为 4，由于 0、1、2、3、4 的二进制形式中 1 的个数分别为 0、1、1、2、1，因此输出数组[0，1，1，2，1]。

方法1 简单计算每个整数的二进制形式中1的个数

分析

计算整数i的二进制形式中 1 的个数有多种不同的方法，其中一种比较高效的方法是每次用“i &（i-1）”将整数i的最右边的 1 变成 0。整数 i 减去1，那么它最右边的 1 变成 0。如果它的右边还有 0，则右边所有的 0 都变成 1，而其左边所有位都保持不变。下面对 i 和 i -1进行位与运算，相当于将其最右边的 1 变成 0。以二进制的1100 为例，它减去 1 的结果是 1011。1100 和 1011 的位与运算的结果正好是 1000。二进制的 1100 最右边的 1变为0，结果刚好就是 1000。

代码

package com.zj.offer.code;

/**
 * 作者: zhoujun134
 * 时间: 2023/12/3 23:43
 */
public class Test3 {

    public static void main(String[] args) {
        int[] result = countBits(4);
        for (int j : result) {
            System.out.println(j);
        }
    }

    public static int[] countBits(int num) {
        int[] result = new int[num + 1];
        for (int i = 0; i <= num; ++i) {
            int j = i;
            while (j != 0) {
                result[i]++;
                j = j & (j - 1);
            }
        }
        return result;
    }
}

如果一个整数共有k位，那么它的二进制形式中可能有 O（k） 个 1。在上述代码中，while循环中的代码对每个整数将执行 O（k） 次，因此，上述代码的时间复杂度是 O（nk）。

方法 2 根据“i &（i-1）”计算i的二进制形式中1的个数

分析

根据前面的分析可知，“i&（i-1）”将i的二进制形式中最右边的 1 变成 0，也就是说，整数i的二进制形式中1 的个数比“``i&（i-1）`”的二进制形式中 1 的个数多 1。我们可以利用这个规律写出如下代码：

代码

    public static int[] countBitsMethod2(int num) {
        int[] result = new int[num + 1];
        for (int i = 1; i <= num; ++i) {
            result[i] = result[i & (i - 1)] + 1;
        }
        return result;
    }

不管整数i的二进制形式中有多少个 1，上述代码只根据 O（1） 的时间就能得出整数i的二进制形式中1的数目，因此时间复杂度是 O（n）。

方法 3 根据“i/2”计算i的二进制形式中1的个数

分析

还可以使用另一种思路来解决这个问题。

如果正整数i是一个偶数，那么i相当于将“``i/2”左移一位的结果，因此偶数i和“i/2`”的二进制形式中1的个数是相同的。

如果 i 是奇数，那么i相当于将“i/2”左移一位之后再将最右边一位设为1 的结果，因此奇数i的二进制形式中1 的个数比“``i/2`”的 1 的个数多 1。

例如，整数3的二进制形式是11，有2个1。偶数6的二进制形式是110，有 2 个 1。奇数7的二进制形式是111，有 3 个 1。我们可以根据3的二进制形式中1的个数直接求出6和7的二进制形式中1的个数。这种解法的参考代码如下所示：

代码

public static int[] countBitsMethod3(int num) {
    int[] result = new int[num + 1];
    for (int i = 1; i <= num; ++i) {
        result[i] = result[i >> 1] + (i & 1);
    }
    return result;
}

这种解法的时间复杂度也是 O(n)

面试题 4：只出现一次的数字

题目： 输入一个整数数组，数组中只有一个数字出现了一次，而其他数字都出现了3次。请找出那个只出现一次的数字。例如，如果输入的数组为 [0，1，0，1，0，1，100]，则只出现一次的数字是100。

分析

这个题目有一个简化版的类似的题目“输入数组中除一个数字只出现一次之外其他数字都出现两次，请找出只出现一次的数字”。任何一个数字异或它自己的结果都是0。如果将数组中所有数字进行异或运算，那么最终的结果就是那个只出现一次的数字。

在这个题目中只有一个数字出现了一次，其他数字出现了3次。相同的3个数字异或的结果是数字本身，但是将数组中所有数字进行异或运算并不能消除出现3次的数字。因此，需要想其他办法。

一个整数是由 32 个 0 或 1 组成的。我们可以将数组中所有数字的同一位置的数位相加。如果将出现3次的数字单独拿出来，那么这些出现了3次的数字的任意第i个数位之和都能被3整除。因此，如果数组中所有数字的第i个数位相加之和能被3整除，那么只出现一次的数字的第i个数位一定是0；如果数组中所有数字的第i个数位相加之和被3除余1，那么只出现一次的数字的第i个数位一定是1。这样只出现一次的任意第i个数位可以由数组中所有数字的第i个数位之和推算出来。当我们知道一个整数任意一位是0还是1之后，就可以知道它的数值。

基于这种思路可以写出如下代码：

代码

   public static int singleNumber(int[] nums) {
        int[] bitSums = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                bitSums[i] += (num >> (31 - i)) & 1;
            }
        }
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) + bitSums[i] % 3;
        }
        return result;
    }

Java的 int 型整数有32位，因此上述代码创建了一个长度为 32 的数组 bitSums，其中“ bitSums[i]”用来保存数组 nums 中所有整数的二进制形式中第i个数位之和。

代码“（num>>（31-i））&1”用来得到整数 num 的二进制形式中从左数起第 i 个数位。整数i先被右移 31-i位，原来从左数起第 i 个数位右移之后位于最右边。接下来与1做位与运算。整数1除了最右边一位是1，其余数位都是0，它与任何一个数字做位与运算的结果都是保留数字的最右边一位，其他数位都被清零。如果整数 num 从左数起第i个数位是1，那么“``（num>>（31-i））&1`”的最终结果就是1；否则最终结果为0。下面求8位二进制整数 01101100 从左数起的第2个（从0开始计数）数位。我们先将 01101100 右移5位（7-2=5）得到00000011，再将它和 00000001 做位与运算，结果为 00000001，即1。8位二进制整数 01101100 从左边数起的第 2 个数位的确是 1。

下面求 8 位二进制整数 01101100 从左数起的第2个（从0开始计数）数位。我们先将 01101100 右移 5 位（7-2=5）得到 00000011，再将它和 00000001 做位与运算，结果为 00000001，即1。8位二进制整数 01101100从左边数起的第2个数位的确是1。

举一反三

题目： 输入一个整数数组，数组中只有一个数字出现 m 次，其他数字都出现 n 次。请找出那个唯一出现m 次的数字。假设 m 不能被 n 整除。

分析：

解决面试题 4的方法可以用来解决同类型的问题。如果数组中所有数字的第 i 个数位相加之和能被n整除，那么出现 m 次的数字的第 i 个数位一定是 0；否则出现m次的数字的第i个数位一定是1。

代码

public static int nNumber(int[] nums, int m) {
    int[] bitSums = new int[32];
    for (int num : nums) {
        for (int i = 0; i < 32; i++) {
            bitSums[i] += (num >> (31 - i)) & 1;
        }
    }
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) + bitSums[i] % m;
    }
    return result;
}

面试题 5：单词长度的最大乘积

题目： 输入一个字符串数组 words，请计算不包含相同字符的两个字符串words[i]和words[j]的长度乘积的最大值。如果所有字符串都包含至少一个相同字符，那么返回0。假设字符串中只包含英文小写字母。例如，输入的字符串数组words为["abcw"，"foo"，"bar"，"fxyz"，"abcdef"]，数组中的字符串"bar"与"foo"没有相同的字符，它们长度的乘积为9。"abcw"与"fxyz"也没有相同的字符，它们长度的乘积为16，这是该数组不包含相同字符的一对字符串的长度乘积的最大值。

分析

解决这个问题的关键在于如何判断两个字符串 str1 和 str2 中没有相同的字符。一个直观的想法是基于字符串str1 中的每个字符 ch，扫描字符串str2判断字符ch是否出现在str2中。如果两个字符串的长度分别为p和q，那么这种蛮力法的时间复杂度是 O（pq）。

方法 1：用哈希表记录字符串中出现的字符

分析

也可以用哈希表来优化时间效率。对于每个字符串，可以用一个哈希表记录出现在该字符串中的所有字符。在判断两个字符串str1和str2中是否有相同的字符时，只需要从'a'到'z'判断某个字符是否在两个字符串对应的哈希表中都出现了。在哈希表中查找的时间复杂度是O（1）。这个题目假设所有字符都是英文小写字母，只有26个可能的字符，因此最多只需要在每个字符串对应的哈希表中查询26次就能判断两个字符串是否包含相同的字符。26是一个常数，因此可以认为应用哈希表后判断两个字符串是否包含相同的字符的时间复杂度是O（1）。

由于这个题目只需要考虑26个英文小写字母，因此可以用一个长度为26的布尔型数组来模拟哈希表。数组下标为0的值表示字符'a'是否出现，下标为1的值表示字符'b'是否出现，其余以此类推。

这种思路的参考代码如下所示：

代码

package com.zj.offer.code;

/**
 * 作者: zhoujun134
 * 时间: 2023/12/4 07:46
 */
public class Test5 {
    public static void main(String[] args) {
        String[] words = {"abcw", "foo", "bar", "fxyz", "abcdef"};
        System.out.println(maxProduct(words));
    }

    public static int maxProduct(String[] words) {
        boolean[][] flags = new boolean[words.length][26];
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                flags[i][c - 'a'] = true;
            }
        }

        int result = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                int k = 0;
                for (; k < 26; k++) {
                    if (flags[i][k] && flags[j][k]) {
                        break;
                    }
                }
                if (k == 26) {
                    int prod = words[i].length() * words[j].length();
                    result = Math.max(result, prod);
                }
            }
        }
        return result;
    }
}

上述代码分为两步。第1步，初始化每个字符串对应的哈希表。如果数组words的长度为n，平均每个字符串的长度为k，那么初始化哈希表的时间复杂度是 $O(nk)$。第2步，根据哈希表判断每对字符串是否包含相同的字符。总共有 $O(n^2)$ 对字符串，判断每对字符串是否包含相同的字符需要的时间为O（1），因此这一步的时间复杂度是 $O(n^2)$。于是这种解法的总体时间复杂度是 $O（nk+n^2）$。

上述代码为每个字符串创建一个长度为26的数组，用来记录字符串中出现的字符。如果数组words的长度为n，那么这种解法的空间复杂度就是O（n）。

方法 2：用整数的二进制数位记录字符串中出现的字符

前面的解法是用一个长度为26的布尔型数组记录字符串中出现的字符。布尔值只有两种可能，即true或false。这与二进制有些类似，在二进制中数字的每个数位要么是0要么是1。因此，可以将长度为26的布尔型数组用26个二进制的数位代替，二进制的0对应布尔值 false，而1对应true。

Java 中 int 型整数的二进制形式有32位，但只需要 26 位就能表示一个字符串中出现的字符，因此可以用一个int型整数记录某个字符串中出现的字符。如果字符串中包含'a'，那么整数最右边的数位为1；如果字符串中包含'b'，那么整数的倒数第2位为1，其余以此类推。这样做的好处是能更快地判断两个字符串是否包含相同的字符。如果两个字符串中包含相同的字符，那么它们对应的整数相同的某个数位都为1，两个整数的与运算将不会等于0。如果两个字符串没有相同的字符，那么它们对应的整数的与运算的结果等于0。

基于这种思路可以写出如下代码：

    public static int maxProductMethod2(String[] words) {

        int[] flags = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            for (char ch : words[i].toCharArray()) {
                flags[i] |= 1 << (ch - 'a');
            }
        }
        int result = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((flags[i] & flags[j]) == 0) {
                    int prod = words[i].length() * words[j].length();
                    result = Math.max(result, prod);
                }
            }
        }
        return result;
    }

上述代码中的整数“flags[i]”用来记录字符串“words[i]”中出现的字符。如果“words[i]”中出现了某个字符ch，则对应的整数“flags[i]”中从右边数起第ch-'a'个数位（即'a'对应最右边的数位，'b'对应倒数第2个数位，其余以此类推）将被标记为1。

如果两个整数“flags[i]”和“flags[j]”的与运算的结果为0，那么它们对应的字符串“words[i]”和“words[j]”一定没有相同的字符。此时可以计算它们长度的乘积，并与其他不含相同字符的字符串对的长度乘积相比较，最终得到长度乘积的最大值。

如果数组 words 的长度为n，平均每个字符串的长度为k，那么这种解法的时间复杂度是 $O（nk+n^2）$，空间复杂度是O（n）。虽然两种解法的时间复杂度和空间复杂度是同一个量级的，但前面的解法在判断两个字符串是否包含相同的字符时，可能需要26次布尔运算，而新的解法只需要1次位运算，因此新的解法的时间效率更高。