当前位置: 首页 > biancheng >正文

由冒泡排序交换数值引发的位操作

再看冒泡排序

    • 翻看B站的视频 讲解算法 说到了冒泡排序中数值交换 发现了一些新的点
      • 注意的点
    • 拓展1
      • 解决方案一
      • 解决方案二
    • 拓展2
      • 方案一
      • 方案二

翻看B站的视频 讲解算法 说到了冒泡排序中数值交换 发现了一些新的点

两个数字交换的操作, 比如交换数字 a 和 b 的数值:

int c = a;
a = b;
b = a;

以上三行代码,完成数值的交换。

但是, 如果不允许使用新的内存,则可有如下方案:

a = a^b;
b = a^b;
a = a^b;
以上三行代码, 完成数值交换

注意的点

进行交换的两个数值 不在内存的同一个区域。

^操作 可以认为是无进位的加操作

拓展1

一个数组中,只存在一个出现奇数次的数字,其余数字均出现偶数次,找出该数字。

解决方案一

构建一个map,遍历数组, key存储数字,value存储出现的次数,遍历完成后统计map中出现奇数次的key即可。

解决方案二

初始化一个整数0,遍历数组,与该数字进行与或操作,遍历结束,即可得到该奇数数字。

拓展2

一个数组中,存在两个出现奇数次的数字,其余均为偶数次,找出这两个数字。

方案一

类似与拓展1中的方案一,可以获取结果

方案二

初始化数字res = 0,全数组遍历,假设两个不通的数字为a 和 b , 则最终结果为 res = a^b, 因为a b 不相同,所以他们必定在 整数的32位上有不通的一位,所以必定存在一个位为一, 找出这一位,然后按照该位为1进行数组遍历,假设此次数组遍历与或 res1, 则最终得到一个数字为res1 为 a b中一个数字,同时可以res ^ res1 得到另外一个数字。

其中提取出res最右边位置为1 的操作为

int rightFistOne = res &(~res +1);

遍历数组中在这里插入图片描述

相关文章:

  • 牛客练习赛#84 F 莫比乌斯反演+杜教筛+技巧+斐波那契数列和gcd的结论+矩阵快速幂
  • ZZNUOJ_用C语言编写程序实现1342:支配值数目(附完整源码)
  • java毕业设计后勤管理系统餐饮评价监督系统(附源码、数据库)
  • 前端基础学习笔记
  • 【TS】联合类型--类型断言--类型推断
  • 谈笑风声的秘密
  • QT影城网上售票系统
  • NetCDF数据在ArcMap中的使用
  • 打怪升级(考验思路)
  • 持续精进,改变自己