[已解决]看见一道题，位运算的脑袋有点懵希望能给解答下

伪侟者

1.         //一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。找出这两个数字（使用位运算）
   
2.         int arr[] = { 1,2,3,4,5,6,7,8,9,10,10,8,7,9,5,3,2,1 };
   
3.         int len = sizeof(arr) / sizeof(arr[0]);
   
4.         int ret = 0;
   
5.         for (int i = 0; i < len; ++i)
   
6.                 // 最后得出ret是这两个数字异或的结果
   
7.                 ret ^= arr[i];
   
8.         // 找到二进制中一的位置
   
9.         int pos;
   
10.         for (int i = 0; i < 8 * sizeof(int); ++i) {
    
11.                 if (((ret >> i) & 0x1) == 1) {
    
12.                         pos = i;
    
13.                         break;
    
14.                 }
    
15.         }
    
16.         // 根据这个位置，将数分为两组
    
17.         int x = 0;
    
18.         int y = 0;
    
19.         for (int i = 0; i < len; ++i) {
    
20.                 printf("%d\n", arr[i] >> pos);
    
21.                 if (((arr[i] >> pos) & 0x1) == 1)
    
22.                         x ^= arr[i];
    
23.                 else
    
24.                         y ^= arr[i];
    
25.         }
    
26.         printf("%d,%d\n", x, y);
    

复制代码

就是根据那个pos吧数组分成两个数组没看懂，希望那位大佬能给解答下

最佳答案

月排行榜 / 总排行榜

tony666

2021-3-22 10:57:10

假设只出现一次的两个数分别是x和y
1. 整体异或一遍  结果是x^y;
2.把x,y分开 ：
   因为 x!= y ,   令 z = x^y ,z ！=0
   z是int型, 一共有8*sizeof(int) 位 ，这么多位一定至少有一位是不同的，（代码里是从低位开始找，找到第一个1）
   只要找到这个1 ，x和 y就区分出来了
   假设这个1在第i位，那么x的第i位和y的第i位一定是不同的（因为异或等于一）
  这样通过判断这一位，分为两组，除了x和y其他数都是成对出现的，所以 结果就出来了。
   
   

跳转到最佳答案楼层

tony666

假设只出现一次的两个数分别是x和y
1. 整体异或一遍  结果是x^y;
2.把x,y分开 ：
   因为 x!= y ,   令 z = x^y ,z ！=0
   z是int型, 一共有8*sizeof(int) 位 ，这么多位一定至少有一位是不同的，（代码里是从低位开始找，找到第一个1）
   只要找到这个1 ，x和 y就区分出来了
   假设这个1在第i位，那么x的第i位和y的第i位一定是不同的（因为异或等于一）
  这样通过判断这一位，分为两组，除了x和y其他数都是成对出现的，所以 结果就出来了。
   
   

伪侟者

tony666 发表于 2021-3-22 10:57
假设只出现一次的两个数分别是x和y
1. 整体异或一遍  结果是x^y;
2.把x,y分开 ：

好的，受教了，如果我把这个增加到三个数只出现一次的，这个要怎么弄

tony666

伪侟者 发表于 2021-3-27 17:53
好的，受教了，如果我把这个增加到三个数只出现一次的，这个要怎么弄

那就不会了