1.2 二进制

整数在计算机中是以二进制的形式表示的。二进制是指数字的每位都是0或1。例如，十进制形式的2转化为二进制形式之后是10，而十进制形式的10转换成二进制形式之后是1010。

位运算是把数字用二进制形式表示之后，对每位上0或1的运算。二进制及其位运算是现代计算机学科的基石，很多底层的技术都离不开位运算，因此与位运算相关的题目也经常出现在面试中。由于人们在日常生活中习惯使用十进制形式，因此二进制及位运算让很多人很难适应。

其实二进制的位运算并不是很难掌握，因为位运算只有6种：非、与、或、异或、左移和右移。非运算对整数的二进制按位取反，0取反得1，1取反得0。下面对8位整数进行非运算：

~00001010=11110101

~10001010=01110101

与、或和异或的运算规律如表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。下面是对8位有符号数值（Java中的byte型整数）进行右移的例子：

00001010>>2=00000010

10001010>>3=11110001

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

00001010>>>2=00000010

10001010>>>3=00010001

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

面试题2：二进制加法

分析：有不少人看到这个题目的第一反应是将二进制字符串转换成int型整数或long型整数，然后把两个整数相加得到和之后再将和转换成二进制字符串。例如，将二进制字符串"11"转换成3，"10"转换成2，两个整数的和为5，将之转换成二进制字符串就得到"101"。这种解法可能会导致溢出。这个题目没有限制二进制字符串的长度。当二进制字符串比较长时，它表示的整数可能会超出int型整数或long型整数的范围，此时不能直接将其转换成整数。

因此，加法操作只能针对两个字符串进行。可以参照十进制加法来完成二进制加法。在进行十进制加法时，总是将两个数字的右端对齐，然后从它们的个位开始从右向左相加同一位置的两个数位，如果前一位有进位还要加上进位。

二进制加法也可以采用类似的方法，从字符串的右端出发向左做加法。与十进制不同的是，二进制是逢二进一，当两个数位加起来等于2时就会产生进位。可以用如下所示的参考代码实现二进制加法：

上述代码中的加法是从字符串的右端开始的，最低位保存在result的最左边，而通常数字最左边保存的是最高位，因此，函数addBinary在返回之前要将result进行翻转。

面试题3：前n个数字二进制形式中1的个数

分析：很多人在面试的时候都能想到直观的解法，使用一个for循环来计算从0到n的每个整数i的二进制形式中1的个数。于是问题转换成如何求一个整数i的二进制形式中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。

这种思路可以用如下代码实现：

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

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

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

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

❖ 根据“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的个数。这种解法的参考代码如下所示：

上述代码用“i>>1”计算“i/2”，用“i&1”计算“i%2”，这是因为位运算比除法运算和求余运算更高效。这个题目是关于位运算的，因此应该尽量运用位运算优化代码，以展示对位运算相关知识的理解。

这种解法的时间复杂度也是O（n）。

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

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

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

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

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

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。

举一反三

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

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

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

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

❖ 用哈希表记录字符串中出现的字符

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

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

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

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

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

❖ 用整数的二进制数位记录字符串中出现的字符

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

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

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

上述代码中的整数“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²），空间复杂度是O（n）。虽然两种解法的时间复杂度和空间复杂度是同一个量级的，但前面的解法在判断两个字符串是否包含相同的字符时，可能需要26次布尔运算，而新的解法只需要1次位运算，因此新的解法的时间效率更高。