Redis 存储结构设计

其他出现两次，只有一个出现一次的那道题我就不更了，直接抑或，最后的结果就是那个数。为什么可以这样做呢？因为一个32位int，如果所有数都出现了两次，那么为1的那些位统计的个数一定是2的倍数，抑或之后全变成0。一个数出现了一次，它为1的那些位上，1的个数必定是奇数，抑或之后一定还是1。

我之前知道出现两次这个题的解法，但是理解的不够深，以为抑或是关键，其实不是，出现了偶数次才是关键。理解了这点，推广到出现3次上，如果所有的出现了三次，那么为1的那些位1的个数一定是三的倍数，那如果有一个数出现了一次呢？没错，它为1的那些以三余模之后，肯定是1。换言之，出现几次都可以用同样的思想解，只不过如果这个重复次数不是偶数，就不能用抑或简单的解决，而是一位一位的用一个量来保存位运算的结果，一看代码就明白了。

还有一个有趣的问题，是剑指offer上的，如果一个数组中只有两个数出现了一次，其他都出现了两次，怎么快速找出这两个数呢？这次的关键是抑或操作。想想把数组抑或之后得到的结果是什么呢？出现两次的数都被自己抑或成了0，对，相当于这两个出现了一次的数的抑或，他们抑或的结果是什么呢？不同的位被置1，相同的位被置0。两个数不同，所以至少有一位被置1了。我们可以根据这一位来分类，这一位为0的归为一类，为1的归为一类，这两类分别抑或，得到的就是要求的那两个数了。

最后还是贴上三次一个的代码：

class Solution {
public:
    int singleNumber(int A[], int n) {
        int res=0;
        for(int i=0;i<32;i++){
            int count = 0;
            for(int j=0;j<n;j++){
                count += (A[j]>>i)&1;
            }
            res |= ((count%3)<<i);
        }
        return res;
    }
};

Redis 存储结构设计,布布扣,bubuko.com

Redis 存储结构设计

原文：http://blog.csdn.net/yfkiss/article/details/23775917