异或寻异

关于异或

a为任意数字：

0 ^ a = a

a ^ a = 0

给出n个数字， 有一个数字只出现奇数次，其余出现偶数次，找出这个数字

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int a[1000005];

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        if(n == 0)
            break;
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &a[i]);
            ans ^= a[i];
        }
        cout << ans << '\n';
    }
    return 0;
}

给出n个数字，有两个数字只出现奇数次，其余出现偶数次，找出这两个数字

更多解析 https://www.jianshu.com/p/cb400b455772

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int a[1000005];

int find_pos(int tem)
{
    int pos = 0;
    while(!(tem & 1))
    {
        tem >>= 1;
        pos++;
    }
    return pos;
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &a[i]);
            ans ^= a[i];
        }
        int res = ans;
        int pos = find_pos(ans);
        for(int i = 0; i < n; ++i)
        {
            if((a[i] >> pos) & 1)
                ans ^= a[i];
        }
        res ^= ans;///ÎÞÐòÊä³ö
        cout << ans << ' ' << res << '\n';
    }
    return 0;
}

给出n个数字，有三个数字只出现一次，其余出现两次，找出这三个数字

设f(n)为n最低位1所在位。

全部异或一次，得 x = a ^ b ^ c.(倘若保证 x != 0问题就像上面一样简单了)

x 不是 a、b、c 中的任一个

（反证：假设x = a, 由 a = a ^ b ^ c 得 b ^ c = 0, 得 b = c, 与题目矛盾）

所以 x ^ a, x ^ b, x ^ c 都不为0，所以f(x ^ a), f(x ^ b), f(x ^ c)都不为0，

那么 y = f(x ^ a) ^ f(x ^ b) ^ f(x ^ c) 也不为0

所以 y 的二进制至少有一位是1，假设其最低位1在M位上

f(x ^ a)	f(x ^ b)	f(x ^ c)	y
0	0	0	0
1	0	0	1
1	1	0	0
1	1	1	1

有以下两种情况：

1.f(x ^ a),f(x ^ b),f(x ^ c)三个式子中只有一个，其第M位是1

2.三个式子第M位皆为1（倘若仅两个式子第M位为1，y的第M位是0）

第二种情况是错误的，反驳如下：

假设2成立，那么 (x ^ a) ^ (x ^ b) ^ (x ^ c) 其第M位 = 1^1^1 = 1,然而

(x ^ a) ^ (x ^ b) ^ (x ^ c) = x ^ x ^ x ^ (a ^ b ^ c) = x ^ x ^ x ^ x第M位为0

根据结论 x ^ a, x ^ b, x ^ c三个式子只有一个，其第M位为0 找到一个数字，再按前面的方法找另两个

Code

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

///a为任意数字:
/// 0 ^ a = a
/// a ^ a = 0
int a[1000005];

int find_pos(int tem)
{
    if(tem == 0)
        return 0;
    int pos = 1;
    while(!(tem & 1))
    {
        tem >>= 1;
        pos++;
    }
    return pos;
}

int main()
{
    int n;
//    freopen("00in.txt", "r", stdin);
    while(~scanf("%d", &n))
    {
        int first = 0;
        int second, third;
        int x = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &a[i]);
            x ^= a[i];
        }
        ///找 f(x ^ a) ^ f(x ^ b) ^ f(x ^ c)
        int y = 0;
        for(int i = 0; i < n; ++i)
        {
            int t = x ^ a[i];
            int tem = find_pos(x ^ a[i]);
            y ^= tem;
        }

        int M = find_pos(y);
        ///利用结论找到第一个特别的数字
        for(int i = 0; i < n; ++i)
        {
            if((   find_pos(x ^ a[i])>>(M - 1)   )  &  1)
                first ^= a[i];
        }
        ///问题简化
        int ans = x ^ first;
        int t = ans;
        ///first丢到后面去
        for(int i = 0; i < n; ++i)
        {
            if(a[i] == first)
            {
                swap(a[i], a[n - 1]);
                break;
            }
        }
        ///找剩余两个数字
        int pos = find_pos(ans);
        for(int i = 0; i < n - 1; ++i)
        {
            if((a[i] >> (pos - 1)) & 1)
                ans ^= a[i];
        }
        second = ans;
        third = t ^ ans;///此输出无序
        cout << first << ' ' << second << ' ' << third << '\n';
    }
    return 0;
}