从“位”到"丢失的数"

写在前面

前几天碰到一道被"全新包装"的经典问题:

Problem 1.1
给定2n+2个数, 其中2n个数两两相同, 另外两个数都是唯一的. 请设计一个算法找出这两个数, 要求使用的空间尽可能的少. 

从一道面试题的角度来讲, 这个问题被包装的很巧妙. 如果应聘者临时抱佛脚地翻阅一遍经典算法题的话, 则很难找到与这个问题的关联; 对于面试官来说, 就更容易淘汰实力不足的应聘者.

本文将从”位“这一个基础的知识模块谈起, 提及编码和位运算, 进而给出这道题目, 以及一系列经典问题的解法.

编码(encoding)

计算机的存储单元是位 (bit) , 每一个位有两个取值, 0和1. 直观地讲, 通过二进制的编码方式, 计算机可以实现对任意长度非负整数的存储. 那么, 实际上计算机是否可以存放“任意长度”的数呢? 通常情况不是的. 底层的数据结构采用静态的存储方式, 因此使用"特定的大小"来存放一个数. 计算机把8个位编制成一个字节 (byte) , 所谓“特定的大小”通常以字节为单位. 举一个例子, 假如我们规定用4个字节 (32位) 来存一个非负整数的话, 那么我们能存储的非负整数 x 满足

$$ 0 \leq x \leq 2^{32}-1 $$

那么, 计算机如何存储一个负整数? 这个问题显然没那么直观. 人们采用在数字前面加一个负号的方法标记一个负数, 而计算机采用一个符号位(sign bit) 来甄别正数和负数.

符号位(sign bit)

符号位放在一个数存储结构的最左边. 对于4个字节 (32位) 表示的整数, 我们用跟前面一样的方式来表示. 这样的话最左边的一位始终是0. 那么我们规定最左边一位是1的数为负数. 但是, 剩下的31位要用怎样的次序来表示负数呢? 用图来举一个例子, 在下图中, 最上面的数和最下面的数, 哪一个来表示-1比较合适? 哪一个来表示绝对值最大的负数比较合适?

$$ 1000...000 $$ $$ 1000...001 $$ $$......$$ $$ 1111...110 $$ $$ 1111...111 $$

答案并不是显而易见的. 计算机科学家们对这件事情产生了分歧, 于是对负数 (联合非负数, 统称为有符号数) 便产生了不同的编码方式. 有原码, 反码, 补码, 移码等. 

移码伴随一个特定的常数 k 而出现. 首先假定用32位来从0开始用二进制表示非负整数, 然后对每一个数减去 k 作为它的真实值. 它可以表示 -k 到 2^32-1-k 的所有整数. 这种编码方法不再遵循符号位规律, 因此不做探讨.

原码很直观地用符号位表示符号, 另外31位表示它的数值. 如, 数值 5 和 -5 仅在最左边一位不同, 分别为000...0101 和 100...0101. 原码有两个0, +0 和 -0 (100...0000) .

反码把一个非负数的所有位取反, 作为它的相反数. 如, 数值 5 和 -5 分别为 000...0101 和 111...1010. 反码也有两个0, +0 和 -0 (111...1111) . 

注意到反码中111...1110表示-1, "下一个数" 111...1111表示-0. 如果把32位编码看成一个环的话, 它的"下一个数"则是000...0000, 表示0. 这样的话, 正数和负数之间便间隔了两个0. 换而言之, -1往后数三个数才能到达1, 四个数才能到达2. 我们为了把这个环变得更加自然, 便采用了补码的编码方式.

补码中, 一个非负数取反再加一作为它的相反数出现. 如, 数值 5 为 000...0101, 取反得到 111...1010, 再加一得到 -5, 111...1011. 这样的话, 多出来的-0消失了, 而 -1 是111...1111, -2 是111...1110, 负数和非负整数被很漂亮地连接在了一起.

为什么补码优于原码和反码? 因为"我们可以在补码环境中忽略符号位直接做竖式加法和竖式减法, 结果不需要做任何转换". 那么, 为什么"我们可以在补码环境中忽略符号位直接做竖式加法和竖式减法, 结果不需要做任何转换"呢? 

因为, 补码相比于非负整数编码, 只是换了一个模2^n的完全剩余系来描述全体整数. 而在同一个模之下, 剩余类与剩余类之间的关系不随剩余系中对应类的代表元素的改变而改变. 

具体的证明请参见<初等数论>中的同余理论. 

我们计算一个数字. n个数位用补码方法表示数的话, 可以表示的范围是多少呢? 我们只需要考虑n位上面的最大数011...1111和最小数100...0000就可以了, 因为它们中间的数被一个不差的表示出来. 考虑到这里, 我们得到答案: 对于n个数位能表示的数 x , x 满足

$$ -2^{n-1} \leq x \leq 2^{n-1}-1 $$

位运算(bitwise operation)

除了整数之外, 计算机中不同类型的数据结构, 全部都是用01编码存储的. 例如我们用1表示True, 0表示False. (当然很多情况下计算机不会只用一个bit来表示一个布尔值) 再如, 我们可以用另一种神奇的方式来表示小数, 进而获得一个表示有限精度实数的方法. 当然这个表示系统要复杂一些, 在此之前, 我们先谈谈"位运算" (bitwise operation). 

位运算有很多种, 比较常见的有 按位取反(NOT), 按位与(AND), 按位或(OR), 按位异或(XOR), 左移, 和右移. 这里先讲前四种. 

首先去掉按位的概念:
取反即把1变成0, 把0变成1, 对应逻辑中的非(NOT);
与即取两个位中较大的一个, 两个数位的与等于1当且仅当两个位都是1, 对应逻辑中的与(AND);
或即取较小值, 两个数位的或等于0当且仅当两个都是0, 对应逻辑中的非(OR);
异或即查看两个数是否相异, 是则为1否则为0. 两个数位的异或等于1当且仅当两个数一个是0另一个是1, 对应逻辑中的异或(XOR).

那么, 按位取反的意思就是把一个的数的每一位都取反; 按位与的意思就是把两个相同数位的数的每一位都进行与操作放在结果中对应的数位上. 比如10101和01101的与的结果就是00101. 或, 异或亦然: 它们都对位进行单独操作.

异或在日常逻辑中出现的不多, 但是在位运算上却非常神奇. 两个相同的数的异或是0; 异或可以表示奇偶性, n个数位做异或操作, 结果就是它们中1的个数, 奇数则1偶数则0. 用异或操作可以巧妙地解决很多难题.

仅举一个例子: 对于0,1,2,3,4,5,6,7这8个数, 我们对它们进行按位异或操作, 得到的结果会是什么呢? 考虑到每一位上1出现的次数都是偶数(对于后三位, 每一位1各出现4次), 我们可以得到一个漂亮的结果.

$$ 000...0000 $$ $$ 000...0001 $$ $$ 000...0010 $$ $$ 000...0011 $$ $$ 000...0100 $$ $$ 000...0101 $$ $$ 000...0110 $$ $$ 000...0111 $$ $$------------(XOR)$$ $$ 000...0000 $$

丢失的数(Missing Number)

我们来看一道经典的问题, 丢失的数.

Problem 0.0
给定n个数, 它们的取值在0到n之间而且两两不同. 注意到在0到n中, 有一个数没有出现在我们给定的数中, 我们称它为"丢失的数". 请设计一个尽量简洁的算法, 来找出这个丢失的数, 要求使用的空间尽可能地少. 

如果你直接想到了把n-1个数先快速排序再从头到尾扫一遍, 那么请打开窗户四处看看风景...

朴素的方法是做一个长度为n的表, 标记一下出现过的数, 之后从头到尾扫一遍这个表, 找到丢失的数. 但是这个方法需要的一定的空间来开一个长度为n的表. 

另一个比较漂亮的做法, 是利用1到n这n个数的求和公式. 对于输入的数, 我们可以直接把它们加起来得到结果 s , 然后用1到n这n个数的和减去 s , 就找到了丢失的数. 注意到这个方法在实际实现的时候不仅需要考虑越界的问题(1到n这n个数的和远远大于n, 可能在当前的数据结构中越界), 而且需要用到加法和乘法, 并不是十分简洁高效.

我们考虑上面位运算的例子. 对0到7这8个数进行异或操作, 得到的结果是0. 原因是从任何一个数位上看, 这8个数中1出现的个数都是偶数 (这个例子适用于从0到2^k-1这2^k个数上面) . 那么, 假如在0到7中间, 有一个丢失的数呢? 考虑把剩下的7个数做一个异或操作, 得到的结果一定是丢掉的那个数. 因为丢失的数的某一位是1当且仅当剩下7个数在那一位上的1出现了奇数次. 那么, 在Problem 0.0 中, 如果n+1是2的幂, 我们就得到了一个解法. 

如果n+1不是2的幂呢? 假如现在0到5中丢失了一个数, 我们有一个非常巧妙的想法: 把输入的序列加上6和7, 这个问题就转化为了0到7之间丢失的数. 换言之, 我们把输入的0到5之间的数异或, 之后再异或6和7, 就可以得到丢失的数.


Answer 0.0
把输入的n个数全部异或起来, 如果n+1是2的幂则终止; 否则继续异或n+1, n+2..., 直到下一个数是2的幂方可终止. 异或的结果一定是丢失的数.

Problem 1.1 的解

我们回到开头的问题, problem 1.1.

Problem 1.1
给定2n+2个数, 其中2n个数两两相同, 另外两个数都是唯一的. 请设计一个算法找出这两个数, 要求使用的空间尽可能的少. 

通过本文的一系列的分析, 我们知道, 假如可以把2n个两两相同的数异或起来, 那么得到的结果一定是0. 不巧的是, 我们除了这2n个数之外, 还有两个不同的数. 事实上, 我们解决了一个更简单的问题.

Problem 1.0
给定2n+1个数, 其中2n个数两两相同, 另外一个数是唯一的. 请设计一个算法找出这个唯一的数, 要求使用的空间尽可能的少.

Answer 1.0
把所有的数异或起来, 得到的数一定是那个唯一的数.

再回到problem 1.1. 我们可以把2n+2个数异或起来, 得到一个数c. 假定之前两个唯一数是a和b, 那么c一定就是a和b异或的结果. 但是我们显然不能通过c来求a和b. 

注意到c一定不是0. 那么c有一个位上一定是1. 考虑2n+2个数在这个位上的情况. 除了a和b之外, 另外2
n个数一定在这个位置上1出现了偶数次, 进而0也出现了偶数次. 而a和b在这个位置上一定是一个0和一个1. 这一点有什么意义呢? 我们换一种说法, 有2x+1个数在这个位上是1, 另外2y+1个数在这个位上是0. 前者有x对数两两相同, 后者有y对数两两相同. 再考虑到problem 1.0, 我们已经得到了解法.

Answer 1.1
把所有的数异或起来得到c. 找到c上面一个为1的位, 对这个位把2n+2个数分类, 这个位上为0的分成第一类, 为1的分成第二类. 把第一类所有的数异或起来得到a, 第二类所有的数异或起来得到b. 那么a和b就是我们要找的那两个数.

交换(SWAP)

以下内容感谢lxg的启发.

我在位运算的一节中, 提到了异或的两个神奇的性质. 第一个是两个相同的数异或的结果为 0 ; 第二个是 n 个数的异或结果相当于它们每一位上 1 的个数, 奇数为 1 偶数为 0 . 事实上异或还有一个很神奇的地方被我漏掉了, 这里打算补充一下.

我们经常需要实现这样一件事情. 假设我们有两个变量 a 和 b , 它们分别存在两块不同的存储空间中, 而且这两块存储空间的大小一致. 现在因为某种需要, 我们必须交换 a 和 b 的值. 注意, 如果我们直接把 a 的存储空间中的内容拿出来, 放进 b 的存储空间中, 那么两块存储空间都会变成 a 的值, 从而我们丢失了 b 原有的值而无法完成交换. 

因此我们通常的做法是另外开一块相同大小的存储空间 c , 用来把 b 原有的值存进去, 再把 a 的值赋给 b, 最后把 c 中的内容 ( b 原有的值) 赋给 a . 这个交换方法叫做三变量交换法. 

然而异或操作可以实现在不开新的存储空间的前提下完成交换. 先把 a 异或 b 的值赋给b, 记做 b' , 再把 a 异或 b' 的值赋给 a, 记做 a' , 最后把 a' 异或 b' 的值赋给 b, 记做b''. 三次操作过后, (a, b) 变成了 (a', b''). 为什么 (a', b'') 就是 (b, a) 呢? 我们略推一下, 即可得出结论. 

$$ b' = a \oplus b $$ $$ a' = a \oplus b' = a \oplus (a \oplus b) = b $$ $$ b'' = a' \oplus b' = b \oplus (a \oplus b) = a $$

事实上一些其他的运算符 (加法, 乘法..) 也可以实现不开新的存储空间完成交换, 但是这些运算符都拘泥于数据结构的限制, 比如两个浮点数, 两个字符就难以用这些运算实现. 事实上, 它们还牵扯到复杂度偏高, 越界等问题. 

异或操作则不需要考虑这些问题. 相比于三变量交换法, 异或交换法的主要劣势体现在实现上. 在上层代码中使用底层的操作很容易产生各种问题, 具体的例子大家可以在网上搜到.

对初学者而言, 异或交换法是不推荐的.

完.