leetcode 位运算之异或

发表于 | 分类于 | 阅读次数:
字数统计: 242 | 阅读时长 ≈ 1 
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>

int main() {
    int a[] = {1, 1, 2, 2, 3, 3, 4, 4, 5};
    int sz = sizeof(a) / sizeof(a[0]);
    int i = 0;
    int x = 0;
    for (i = 0; i < sz; i++) {
        x ^= a[i];    //将所有的数异或一下
    }
    printf("%d\n", x);
    return 0;
}

任何一个数字 异或它自己都等于0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<stdio.h>

int main() {
    int a[] = {1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7};
    int i = 0;
    int sz = sizeof(a) / sizeof(a[0]);
    int n = 0;
    int pos = 0;
    int x = 0;
    int y = 0;
    for (i = 0; i < sz; i++) {
        n ^= a[i];       //将所有的数异或 得到 6^7 的结果
    }
    for (i = 0; i < 32; i++) {
        if (((n >> i) & 1) == 1) {
            pos = i;   //找到 6^7 的二进制数中为1的一位
            break;
        }
    }
    for (i = 0; i < sz; i++)    //开始分组
    {
        if (((a[i] >> pos) & 1) == 1) {
            x ^= a[i];    //得到一个数
        } else {
            y ^= a[i];       //得到另一个数
        }
    }
    printf("%d  %d\n", x, y);
    return 0;
}