VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 294|回复: 3

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

[复制链接]
79_avatar_middle
最佳答案
0 
在线会员 发表于 2021-3-21 00:45:24 | 显示全部楼层 |阅读模式
  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吧数组分成两个数组没看懂,希望那位大佬能给解答下
最佳答案
70_avatar_small
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其他数都是成对出现的,所以 结果就出来了。
   
   




上一篇:为什么Unicode的情况下无法输出汉字呢?
下一篇:麻烦帮忙讲解下,各位大佬,感谢
70_avatar_middle
最佳答案
44 
在线会员 发表于 2021-3-22 10:57:10 | 显示全部楼层    本楼为最佳答案   
bestAnswer
假设只出现一次的两个数分别是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其他数都是成对出现的,所以 结果就出来了。
   
   
79_avatar_middle
最佳答案
0 
ico_lz  楼主| 发表于 2021-3-27 17:53:00 | 显示全部楼层
tony666 发表于 2021-3-22 10:57
假设只出现一次的两个数分别是x和y
1. 整体异或一遍  结果是x^y;
2.把x,y分开 :

好的,受教了,如果我把这个增加到三个数只出现一次的,这个要怎么弄
70_avatar_middle
最佳答案
44 
在线会员 发表于 2021-3-29 08:59:10 | 显示全部楼层
伪侟者 发表于 2021-3-27 17:53
好的,受教了,如果我把这个增加到三个数只出现一次的,这个要怎么弄

那就不会了看见一道题,位运算的脑袋有点懵希望能给解答下
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

×【发帖 友情提示】
1、请回复有意义的内容,请勿恶意灌水;
2、纯数字、字母、表情等无意义的内容系统将自动删除;
3、若正常回复后帖子被自动删除,为系统误删的情况,请重新回复其他正常内容或等待管理员审核通过后会自动发布;
4、感谢您对VC驿站一如既往的支持,谢谢合作!

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号-4 )|网站地图wx_jqr

GMT+8, 2021-5-9 04:05

Powered by CcTry.CoM

© 2009-2021 cctry.com

快速回复 返回顶部 返回列表