位运算的探究

天空的代码世界 2020-05-14

129

写于 2014-10-10：给学弟出了一道题，告诉你n个数，其中只有一个数出现一次，其他的数都出现三次。求出现一次的那个数。

前言

2020年05月，有人问我一道题，一想，6年前曾研究过，找到当时的文章，分享出来。

文章1：位运算的探究 http://github.tiankonguse.com/blog/2014/10/10/bit-operation.html
文章2：n-m 问题 http://github.tiankonguse.com/blog/2014/10/22/n-m-problem.html

由于有人没看明白起初的O(n)操作，所以这里就先简单的介绍一下 O(n log(n))的做法。

我这里添加上基本的做法，然后把O(n)做法的分析写的更详细了一个，明白的人可能看起来比较啰嗦，抱歉了。

另外有人问假设是大部分都是4个相同，只有一个是2个相同怎么做，这个问题我们可以称为4-2问题。

为了不偏离主题，我重新写一篇文章专门讨论 n-m 问题。
这篇文章主要讲解的就是 3-1 问题了。

如果你不想看基本做法，可以直接跳到问题的来源的位置。

基本做法

最暴力的方法

最暴力的方法就是排序了，当然也可以 map 计数。

可以选择的排序有快速排序、基数排序等吧，都是 O(n log(n)) 的算法。

声明基数排序看起来是 O(32n) 的复杂度，其实就是 O(n log(n)) 的复杂度。
32位整数最大为 2^32 ，log(2^32) = 32 log(2)，因此 32 就可以近似理解为 log 级别的了。

排序后我们就顺序统计了，遇到不是三个连续的了，就找到答案了。

聪明的位运算做法

由于只有32位，我们可以开一个32位的数组，然后遍历所有的数字时，数字每一位都加到数组对应的位置中，然后模3。

这样最后数组中肯定都是0或1，这些0和1组成的二进制数字就是答案了。

这个做法看起来很巧妙的样子，而且可以解决那种 n-m 问题(n>m)，只需要模n即可。
但是复杂度实际上还是没有什么改进，依旧是 O(n log(n)) 的复杂度。

问题的来源

学弟发给我一个代码，第一眼竟然没看明白。

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];
}

然后想到，可能用到了位运算的一些规律，比如分配率，结合律，交换律等。

异或的一些公式

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 ^ (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 & ~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。

实际上可以看出，对于 0，不影响 one 和 two 的值。

对于 1，状态转移如下：

0 0 => 1 0
1 0 => 0 1
0 1 => 0 0

one 的转移推导

下面我们先看 one 的值是怎么转移的

我们可以看到，a ^ one1 后，只有最后一个和 one2 不一样。本来为 0 的值却为 1 了。

所以我们需要和一个数字进行一种操作，把最后那个 1 变为 0，而且其他行的值应该保持不变。

那我们现在有哪些已知的值呢？

比较简洁的值有下面几个。

可以看到，比较简洁的候选人有 a、~a、one1、~one1、two1、~two1。

我们要选择一个，和 a ^ one1 进行一种操作，来得到 one2。

比较简洁的操作有 | 、&、^ 这三种。

经过大量的尝试，我们可以发现 ~two0 候选人和 & 操作获得胜利，成功的得到 one2。

于是我们得到第一个 one 转移的公式

one2 = (a ^ one1) & ~two1;

two 的转移推导

接下来我们再看看 two 的值是怎么转移的。

我们惊奇的发现，a ^ two 后，也是只有一位和 two2 不同，而且也是本来该是 0 的却变为 1 了。

我们枚举找出候选人(a、~a、one1、~one1、two1、~two1、one2、~one2)和候选操作(|、&、^)。

由于第一个是 & 操作找到的，我们这次当然先看 & 操作了。

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

使用公式表达清晰一些

0 0 => 1 0
1 0 => 1 1
1 1 => 0 0

此时状态转移表是

这时使用异或后有什么发现呢？

这个公式用上面的方法很容易推导的，大家可以推导一下。

大家自己可以想想，方法多多，关键在于你怎么去想。

《完》

-EOF-

题图：来自朋友圈。

上篇文章：Google C++代码规范：头文件

推荐：2020 腾讯程序设计竞赛（二）

长按二维码，一起成长学习

▲ 长按关注，天天成长

觉得有帮助可以点击好看与转发，谢谢！

数据库

文章转载自天空的代码世界，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

位运算 的探究

前言