|
在解决问题前需要了解三个位运算知识：
1.任何一个数和0按位异或就是其自身。例如：2^0=0；0000 0010 ^ 0000 0000 = 0000 0010
2.任何一个数和其自身按位异或结果为0。例如：2^2=0；0000 0010 ^ 0000 0010?= 0000 0000
3.找到最低位为1，其余位为0的那个数，代码可表示为
num=num&-num 或 num=num&~(num-1)。例如：3&(-3)=1；0000 0011 & 1111 1101 = 0000 0001
算法思想：
考察分堆的思想
step1：先将所有的数异或，得到异或后的结果num
step2：找出最低位为一的那一个数result
step3：将所有的数与分割值result按位与，就会把原有的数分为俩堆
step4：分开后对各自的那一堆进行异或，得到那个单独的数
（1）对于用num与一组数：3，2，5，8，6，5，2，3 依次按位异或的意义可以参照
4.【C语言】101个整数中有50个数出现了两次，1个数出现了一次， 找出出现了一次的那个数
而在这组102个数中，有50个数字成对出现，还有两个单独出现。则逐个按位与后得到num=14，这个结果也为 8 和 6 按位异或的结果。
（2）此时需要找到一个数值result将这组数分成两堆，每一个堆出现一个单独的数。然后在对每个堆中的元素进行一次按位异或操作，最后得到两个独立的数。
我们来理解计算得到result的意义：
8? ? ? ? 0000 1000????????????????????????????????????????????????
6? ? ? ? 0000 0110? ? ? ? ^
14? ? ? 0000 1110? ? ? ? num?????????
可以看到如果num的某一位出现1，必然是两个数对应的相同比特位，一个为1，另一个为0，异或得到的。所以取num中某一位为1，其余位为0，组成result。通常取result从右往左数最低位为1，其余位为0的数。如：num = 0000 1110，则取 result = 0000 0010 。???????
得到result通常有两个方法：
(1)? result = num&-num
(2) 令 i=1,利用循环寻找num&i != 0 的 i?值，如果一直运算为0，则 i 不断按位左移，直到运算得1。
while（（num & i）== 0）
? ? ? ? a<<1;
?则通过result=0000 0010 必然能将这组数分成两堆。例如result与6进行按位与得到1；result与8进行按位与得到0，而result与其他数按位与也会得到1和0两种情况。
（3）用result依次和每一个数进行按位与，就会遇到结果为0和1。结果为1的arr[i]和first进行按位异或；结果为0的arr[i]和second进行按位异或。最后会得到两个出现1次的数：first和second。
代码如下：
#include<stdio.h>
int main()
{
int arr[8] = { 3,2,5,8,6,5,2,3 };
int i, result,num=0;
int first=0, second=0;
//1.先将所有的数异或，得到异或后的结果num
for (i = 0; i < sizeof(arr) / sizeof(int); i++) {
num ^= arr[i];
}
//2.找出最低位为一的那一个数result
result = num & -num;
for ( i = 0; i < sizeof(arr) / sizeof(int); i++)
{
//3.将所有的数与result按位与，就会把原有的数分为俩堆
if (result&arr[i])
{
//4.分开后对各自的那一堆进行异或，得到那个单独的数
first ^= arr[i];
}
else
{
second ^= arr[i];
}
}
printf("%d %d\n", first, second);
return 0;
}
|