【位运算】怕位运算?有我你何足畏惧

简介: 【位运算】怕位运算?有我你何足畏惧

如果你是第一次了解位运算,或者对位运算还不熟,请移步位运算

操作对象:整数的补码

位运算,位即是二进制位,而以二进制位方式存储的数据就是整数,而非浮点数

且位运算的对象是补码.

综合来看位运算的操作对象就是整数的补码

下面只提供关键代码及适当分析

1.求一个整数的二进制位中1的个数

1-1方法1:除2取余法

简单,但是缺陷明显,负数不管用(负数取余有负数,而二进制只有0和1)

int len=0;
while (n)
  {
    a[len++] = n % 2;
    n /= 2;
  }
printf("这个整数的二进制位中1有%d个",len);

1-2方法2:右移与1法

  1. 巧妙利用1的补码只有最后一位是1,其余皆是0
  2. 利用1的补码特性,使得结果的补码最后一位可能时0或1,其余皆是0
  3. 右移,使n的补码依次和1的补码按位与
  4. 只有n补码最后一位为1时才为1
  5. count计数,移动完32个比特位结束
for (int i = 0; i < 32; i++)
{
  if ((n >> i) & 1 == 1)
  {
    count++;//count计数
  }
}
printf("这个整数的二进制位中1有%d个",count);

1-3方法3:按位与n-1法

  1. 巧妙利用,当n!=0时,n和n-1的二进制的补码的最后一位肯定是一个1,一个0
  2. 每次循环后最后一位得到按位与0,同时能消去补码中的一个1
  3. 当n==0时,循环终止,count循环的次数即是二进制位中1的个数
while (n)
{
  int count = 0;
  n=n&(n-1)
  count++;
}
printf("这个整数的二进制位中1有%d个",count);

2.判断一个正数是不是2的整数次方

  1. 2的整数次方例如2,4,8,16,对应的补码中皆是只有一个1
  2. 使这个数丢失一个1,整体结果为0则证明是2的整数次方
if(n&(n-1)==0)
printf("该数是2的整数次方");

3.整数a改变多少处可以得到b整数

  1. 按位异或可标记整数a,b的补码中不同的地方为1
  2. 问题转化为求1异或后的结果中1的个数,酷似问题1
int n = a ^ b;
while (n)
{
  int count = 0;
  n=n&(n-1)
  count++;
}
printf("整数a改变%d处可以得到b整数",count);

4.不使用加减法求整数a和整数b的和

本题我有细讲过,速戳 不使用加减法求整数a和整数b的和

while (num2)
{
  int temp = num1 | num2;
  num2 = (num1 & num2) << 1;
  num1 = temp;
}
printf("两个数的和是:%d", num1);

5.不引入第三个变量交换整数a,b的值

本题我有细讲过,速戳交换ab两数的三种方法

printf("交换前:a=%d\tb=%d\n", a, b);
a = a ^ b;
b = a ^ b;
a = a ^ b;
printf("交换后:a=%d\tb=%d\n", a, b);

6.找出混杂在情侣堆中的一个单身狗

问题描述:数组{1,2, 2, 3 , 3 ,4, 4} ----------> return 1;

酷似问题5:

  • 巧妙利用异或的交换律和结合律
  • a^a=0
int ans = 0;
for (int i = 0; i < n - 1; i++)
{
  ans = ans ^ a[i];
}
printf("单身狗是;%d\n", ret);

6-1变式:分配对象

问题描述:如果1,2,3…n丢失了一个数据,让你用位运算的知识找到他

题解思路:

这里好像都是单身狗,那就给他们^异或1,2,3…n,我愿称之为分配对象,没有领到对象的就是那个丢失的数据.

也就是a[0]^ a[1]^ a[2]^ a[3]…a[n]^ 1^2 ^3 ^ 4… ^ n

7找出混杂在情侣堆中的两个单身狗

问题描述:数组{1,2, 3 , 3 ,4, 4} ----------> 找出 1和2;


设两个单身狗分别为x和y,假设第一次异或的结果为ans


先回顾对异或的理解:标记二进制位中不同处位为1


整体异或一次得到结果(ans)的二进制位如果某一位(第一个二进制位为1处)为1,则x,y的二进制的该位必定一个为0一个为1

按照某个位置(pos)的二进制位为0还是1将数组分为两部分,只要pos位置为1的数组元素再异或一次就能找到x

y=ans^x

int main()
{
  int a[6] = { 1,2,3,3,4,4};
  int ans = 0;
  //进行第一次异或找到ans
  for (int i = 0; i < 6; i++)
  {
    ans = ans ^ a[i];//两个单身狗异或第一次得到ans
  }
    //通过ans找到其二进制中第一个二进制位为1的位置,记为pos
  int pos = 0;
  for (int i = 1; i <= 32; i++)//遍历32个比特位
  {
    if ((ans >> i) & 1 == 1)
    {
      pos = i;
      break;//找到第一个二进制位为1的位置后跳出
    }
  }
  int x = 0;
  for (int i = 0; i < 6; i++)//遍历6个数组元素
  {
    if((a[i]>>pos)&1==1)//将数组中二进制位pos位置为1的归到这里参与异或
      {
        x=x^a[i];//异或第二次得到第一个单身狗
      }
  }
  int y = 0;
  y=x^ans;//小技巧
    printf("单身狗分别是:%d和%d",x,y);
    return 0;
}

本题注释中的小技巧:由ans(3)和x(2)求y(1)的原理

1 ^ 2=3

3 ^ 2=3 ^ 1 ^ 1 ^ 2=3 ^ 1 ^ 3 =1

关注我一起成长

目录
相关文章
|
存储 XML 弹性计算
Zotero+阿里云盘文献同步
通过将阿里云盘映射为WebDav,作为Zotero的文献同步网盘,实现了多设备上的Zotero文献同步
Zotero+阿里云盘文献同步
|
数据可视化 Java uml
IDEA这个功能真强大!一键把整个项目代码绘制成UML类图...
IDEA这个功能真强大!一键把整个项目代码绘制成UML类图...
5360 0
IDEA这个功能真强大!一键把整个项目代码绘制成UML类图...
|
11月前
|
运维 监控 网络协议
网络诊断必备:Ping、Traceroute、Wireshark的实用技巧详解
网络诊断必备:Ping、Traceroute、Wireshark的实用技巧详解
2168 0
|
12月前
|
小程序
微信小程序之weui.wxss不能引用查找的解决方案
微信小程序之weui.wxss不能引用查找的解决方案
300 0
|
前端开发 JavaScript Java
阿里云OSS临时凭证前后端配合上传文件
阿里云OSS临时凭证前后端配合上传文件
489 0
|
JavaScript
如何运行vue项目(维护他人的项目)
如何运行vue项目(维护他人的项目)
570 0
|
API 开发工具 Android开发
从安装到打包,手把手教你如何在Uno Platform上部署跨平台应用——一篇详尽的开发者指南
【9月更文挑战第7天】Uno Platform 是一个跨平台应用开发框架,利用UWP API构建Web、iOS、Android等多平台应用。本文详述了安装Uno Platform SDK、配置项目支持跨平台、添加主方法以及使用命令行工具进行应用打包的过程,助您快速上手 Uno Platform 并部署应用。通过简单的代码示例,让开发者轻松掌握从安装到发布的核心步骤。
886 2
|
前端开发
css 实用技巧 —— div在div中水平垂直居中(两种方法)
css 实用技巧 —— div在div中水平垂直居中(两种方法)
462 3
|
Shell Windows
Mac使用IntelliJ IDEA报错“Unable to save settings: Failed to save settings. Please restart IntelliJ IDEA”
Mac使用IntelliJ IDEA报错“Unable to save settings: Failed to save settings. Please restart IntelliJ IDEA”
Mac使用IntelliJ IDEA报错“Unable to save settings: Failed to save settings. Please restart IntelliJ IDEA”
|
弹性计算
阿里云服务器ip地址是多少啊怎么查看?
阿里云服务器ip地址是多少啊怎么查看?
730 2