位运算 的探究
作者: | 更新日期:
给学弟出了一道题, 告诉你n个数, 其中只有一个数出现一次, 其他的数都出现三次.求出现一次的那个数.
本文首发于公众号：天空的代码世界，微信号：tiankonguse
前言
PS:更新时间 2014-10-22.
由于有人没看明白起初的O(n)操作, 所以这里就先简单的介绍一下 O(n log(n))的做法.
我这里添加上基本的做法, 然后把O(n)做法的分析写的更详细了一个, 明白的人可能看起来比较啰嗦, 抱歉了.
另外有人问假设是大部分都是4个相同, 只有一个是2个相同怎么做, 这个问题我们可以称为4-2问题.
这样的话这篇文章主要讲解的就是3-1问题了.
为了不偏离主题, 我重新写一篇文章专门讨论 n-m 问题.
如果你不想看基本做法, 可以直接跳到 问题的来源 的位置, 向下滚动的时候, 应该可以看到有个目录, 点击 问题的来源 即可.
基本做法
最暴力的方法
最暴力的方法就是排序了.
可以选择的排序有 快速排序, 基数排序等吧, 都是 O(n log(n)) 的算法.
声明基数排序看起来是 O(32n) 的复杂度, 其实就是 O(n log(n)) 的复杂度.
32位整数最大为 2\^32 , log(2\^32) = 32 log(2), 因此 32 就可以近似理解为 log 级别的了.
排序后我们就顺序统计了, 遇到不是三个连续的了, 就找到答案了.
聪明的位运算做法
由于只有32位, 我们可以开一个32位的数组, 然后遍历所有的数字时, 数字每一位都加到数组对应的位置中, 然后模3.
这样最后数组中肯定都是01,, 这些01组成的数字就是答案了.
这个做法看起来很巧妙的样子, 而且可以解决那种 n-m 问题(n>m),只需要模n即可.
但是复杂度实际上还是没有什么改进, 依旧是 O(n log(n)) 的复杂度.
问题的来源
学弟发给我一个代码, 第一眼竟然没看明白.
int run(int n, int* A) {
int ones = 0;// 出现一次的标志位
int twos = 0;// 出现第二次标志位
for(int i = 0; i < n; i++) {
ones = (ones ^ A[i]) & ~twos;// 第二次出现的去掉, 第一次出现的加上, 第三次出现的不变
twos = (twos ^ A[i]) & ~ones;// 第一次出现的不变, 第二次出现的加上, 第三次出现的去掉
}
return ones;
}
然后想到, 可能有位运算的一些规律, 比如分配率, 结合律, 交换律等.
异或的一些共公式
a op b
a | b = b | a
a & b = b & a
a ^ b = b ^ a
~~a = a
~(a & b) = (~a) | (~b)
~(a | b) = (~a) & (~b)
~(a ^ b) = (~a) ^ b = a ^ (~b) = ~((~a) ^ (~b))
a op ( b op c)
a & (b | c) = (a & b) | (a & c)
a & (b ^ c) = (a & b) ^ (a & c)
a | (b & c) = (a | b) & (a | c)
a | (b ^ c) = (a | b) ^ (~a & c)
a ^ (b | c) = ?
a ^ (b & c) = ?
(a | (b & c )) & ~(b ^ c) = ?
a op ( a op c)
| a | b | a ^ (a | b) | a ^ (a&b) | a | (a ^ b) | a | (a&b) | a&(a | b) | a&(a ^ b) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
a ^ (a | b) = ~a & b
a ^ (a & b) = a & ~b
a | (a ^ b) = a | b
a | (a & b) = a
a & (a ^ b) = a ^ (a & b) = a & ~b
a & (a | b) = a
高级推导公式
| a | b | (a ^ b)&(a&b) | ~(a ^ b)&(a&b) | ~(a ^ b)|(a&b) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
a & ~a = 0
(a ^ b) & (a & b) = (a ^ b) & a & b = 0
~(a ^ b) & (a & b ) = a & b
~(a ^ b) | (a & b ) = ~(a ^ b)
代码的研究
我对异或的那些公式推导了一番, 也没推导出来什么.
后来学弟告诉我原理是：
原理
- 默认one,two都是0, 即任何数字都不存在
- 数字a第一次来的时候, one标记a存在, two不变
- 数字a第二次来的时候, one标记a不存在, two标记a存在
- 数字a第三次来的时候, one不变, two标记a不存在
分析
由于一直是异或, 没有左移或右移, 所以我们可以看成n个数字每一位每一位做了某些位操作而得到答案的.
只看一位后发现问题突然简单了.
因为只看一位的话, 就只有0和1了.
我们先不看只出现一次的那个数, 其他数字合起来就是每一位都出现了 3n 次0 和 3m 次1.
加上只出现一次的那个数, 就是告诉你若干个0,1. 其中有一个数字是 3n+1 个, 另外一个是3m个.
由于默认值是0, 所以我们只需要对1操作, 即操作所有数后, 剩下的是1答案就是1, 剩下的是0答案就是0.
注：假设1是3m个, 0是3n+1, 则操作完1后, 1刚好消去, 答案刚好是0了.
假设0是3m个, 1是3n+1, 则操作完1后, 1还剩一个, 答案也应该是1.
下面我看先看一下原理对应的图表.
实际上就是一个状态机,从(0,0)出发, 相同状态作用与0和1.
| a | one1 | two1 | one2 | two2 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 |
实际上可以看出, 处于0, 不影响one和two的值.因为假设1有3个, 操作完后就是0, 答案就是0, 所以对于0我们只需要什么都不做.
one 的转移推导
下面我们先看 one 的值是怎么转移的
| a | one1 | a ^ one1 | one2 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
我们可以看到, a ^ one1 后, 只有最后一个和 one2 不一样.本来为 0 的值却为 1 了.
所以我们需和一个数字进行 一种操作, 把最后那个 1 变为 0, 而且其他行的值应该保持不变.
那我们现在有哪些已知的值呢？
比较简洁的值有下面几个.
| a | ~a | one1 | ~one1 | two1 | ~two1 | a \^ one1 | one2 |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
可以看到, 比较简洁的候选人有 a, ~a, one1, ~one1, two1, ~two1.
我们要选择一个, 和 a ^ one1 进行一种操作, 来得到 one2.
| 比较简洁的操作有 | , & , ^ 这三种. |
进过大量的尝试, 我们可以发现 ~two0候选人 和 &操作获得胜利, 成功的得到 one2.
于是我们得到第一个 one 转移的公式
one2 = (a ^ one1) & ~two1;
two 的转移推导
接下来我们再看看 two 的值是怎么转移的.
| a | two1 | a ^ two1 | two2 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 |
我们惊奇的发现, a ^ two 后, 也是只有一位和 two2 不同, 而且也是本来该是 0 的却变为 1 了.
| 我们改进找出候选人(a, ~a, one1, ~one1, two1, ~two1, one2, ~one2)和候选操作( | , &, ^). |
| a | ~a | one1 | ~one1 | one2 | ~one2 | two1 | ~two1 | a ^ two1 | two2 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
由于第一个是 & 操作找到的, 我们这次当然先看 & 操作了.
a ^ two1 是 0 的那些行不用看了, 因为 0 任何数都是0.
我们只需要看 a ^ two1 是 1 的那些行.
对于第二行, 我们需要找出是0的列, 对于其他的行, 我们需要找到是1的列, 这样才能得到 two2.
第二行, 是 0 的列有 ~a, one1, ~one2, two1, 这些成员临时入选.
第四行, 临时候选列中 有 1 的列有 one1, ~one2, 这些成员再次临时入选, 竞争很激烈, 每次减半, 相信下次就没有了.
第五行, 临时候选中由 1 的列只有 ~one2 了, 进入了临时候选.
最后, 由于所有的都遍历完了, ~one2 获胜, 于是公式找到了.
two2 = (a ^ two1) & ~one2;
综合分析
上面的两个式子已经很简洁了.
one2 = (a ^ one1) & ~two1;
two2 = (a ^ two1) & ~one2;
one1 = one2；
two1 = two2；
发现我们不需要 one2 和 two 这两个变量了, 于是公式简化为
one = (a ^ one) & ~two;
two = (a ^ two) & ~one;
此时, 我们就得到了和最开始写的那个公式一样的结论了.
java代码的答案
其实, 最开始学弟给我的程序不是这个简洁的cpp写的程序, 而是一个java写的程序.
我之所以推导异或的式子也是因为下面的程序.
看下面的最开始的程序.
public int singleNumber(int[] A) {
if(A.length == 1) return A[0];
// A[0] is correct to start
// Take care of processing A[1]
A[0] ^= A[1];
// Set A[1] to either 0 or itself
A[1] = (A[0]^A[1])&A[1];// => A[1] = A[0] & A[1];
// Continue with algorithm as normal
for(int i = 2; i < A.length; i++){
A[1] |= A[0]&A[i];
A[0] ^= A[i];
A[2] = ~(A[0]&A[1]);
A[0] &= A[2];
A[1] &= A[2];
}
return A[0];
}
由于程序对前两个数特判了, 我们可以用两个变量替换, 这样就可以从0开始循环了.
public int singleNumber(int[] A) {
int one = 0, two=0, tmp;
for(int i = 0; i < A.length; i++){
two = two | (one & A[i]);
one = one ^A[i];
tmp = ~(one & two);
one = one &tmp;
two = two &tmp;
}
return A[0];
}
看起来好复杂的样子, 我给他再合并一下.
public int singleNumber(int[] A) {
int one = 0, two=0, tmp;
for(int i = 0; i < A.length; i++){
tmp = ~((one ^A[i]) & (two | (one & A[i])));
two = (two | (one & A[i])) & tmp;
one = (one ^A[i]) & tmp;
}
return A[0];
}
看着还是好复杂的样子, 这时我上面的那些异或公式就派上用场了.
可以先对 tmp 展开.
tmp = ~((one ^ a) & (two | (one & a)))
=> ~( ((one ^ a) & two) | ((one ^ a) & (one & a)) ) // 按 a & (b | c) = (a & b) | (a & c) 展开
=> ~ ((one ^ a) & two) //(one ^ a) & (one & a) 恒等于 0
=> ~(one ^ a) | ~two
然后对 two 展开
tmp = ~(one ^ a) | ~two
one2 = (one ^ a) & tmp
= (one ^ a) & (~(one ^ a) | ~two)
= ((one ^ a) & ~(one ^ a)) | ((one ^ a) & ~two)
= (one ^ a) & ~two
two2 = (two | (one & a)) & tmp
= (two & tmp) | ((one & a) & tmp )
= (two & (~(one ^ a) | ~two)) | ((one & a) & tmp )
= (two & ~(one ^ a)) | (two & ~two) | ((one & a) & tmp )
= (two & ~(one ^ a)) | ((one & a) & tmp ) // (two & ~two) 恒等于 0
= (two & ~(one ^ a)) | ((one & a )& (~(one ^ a) | ~two) )
= (two & ~(one ^ a)) | (((one & a ) & ~(one ^ a)) | ((one & a ) & ~two))
= (two & ~(one ^ a)) | ((one & a ) | ((one & a ) & ~two) )
= (two & ~(one ^ a)) | (one & a )
= (two | (one & a )) & (~(one ^ a) | (one & a ))
= (two | (one & a )) & ~(one ^ a)
化简到哪里就化简不动了, 但是经过分析, 发现对于 one, a 和 two.
- one 和 a 同时为0的时候, two2=two, one2=0
- one 和 a 同时为1的时候, two2=1, one2=0
- one 和 a 不同时, two2 = 0, one2 = ~two
此时再想想那原理
- one 和 a 同时为0, one和two的值不变, 因为 a=0.
- one 和 a 同时为1, 说明是第二个1. two应该标记为1, one标记为0
- 如果a为0, 则one为1, two肯定为0, ~two还是1, 即保持不变
- 如果a为1, 则one为0, 此时two可能是0或1.
- 如果two为0, 这时来一个1, 应该标记one=1, 即这是第一个1.
- 如果 two 为1, 这时来一个1, 说明是第三个1, 则one=two=0.
java 代码为什么这么复杂
前面我们说原理了, 也就是那张表.
有了表, 我们只要通过某些公式得到那种表就行了.
但是我们怎么样才能找到那些公式就是一个问题了, 那个cpp代码找到了一种简洁的公式, 但是这个java代码就没有那么幸运, 找到这么复杂的公式.
经过我的化简, one 的求值已经简化到和cpp的one一样的求值公式了.
但是java的第二个就没有那么幸运了, 化简到相对最简时还是有些复杂.
当然java的第二个公式可能还可以化简, 但是我时间有限, 没有时间去化简, 所以读者可以自己尝试化简一下.
其他方法
有了那个原理的思路, 我们可以用另一种思路来试试.
- 来第一个1时 one 标记为1
- 来第二个1时 two 标志为1
- 来第三个1时, one和two重置为0
此时状态转移表是
| a | one1 | two1 | one2 | two2 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 |
这时使用异或后有什么发现呢？
| a | one1 | ~one1 | two1 | ~two1 | a \^ one1 | a \^ two1 | one2 | two2 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
这个公式用上面的方法很容易推导的, 大家可以推导一下.
大家自己可以想想, 方法多多, 关键在于你怎么去想.
本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。
