位运算 - 初见

举报
看,未来 发表于 2020/12/29 23:24:38 2020/12/29
【摘要】 以前也多多少少接触过一点位运算,课本上,LeetCode上,但是就是没有动手实操过,因为没遇到那个场景。。 我一度不知道位运算干嘛用,昨天在《编程珠玑》上看到一个位运算解决大数排序的问题,突然我就对这个技术有了兴趣。 文章目录 位运算 VS 普通运算位运算运算符按位与 &按位或 |按位异或 ^按位取反左移位运算符 <<右移位运算符 >>负数的二进...

在这里插入图片描述

以前也多多少少接触过一点位运算,课本上,LeetCode上,但是就是没有动手实操过,因为没遇到那个场景。。
我一度不知道位运算干嘛用,昨天在《编程珠玑》上看到一个位运算解决大数排序的问题,突然我就对这个技术有了兴趣。

位运算 VS 普通运算

其实我个人觉得没有什么可比性,这两种运算,要说它们属于不同领域也是可以的,位运算是位运算,普通运算是普通运算。
不过吧,位运算快一点,程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了,就是直接对整数在内存中的二进制位进行操作。
由于位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。
但是吧,数据量小的时候也看不出什么区别来,不过数据量大的话,嘿嘿,我也没试过。

多学点总是好的,技多不压身嘛。

位运算运算符

按位与 &

相同位的两个数字都为1,则为1;若有一个不为1,则为0。

示例:6&11

	0 1 1 0
	1 0 1 1
&-----------
	0 0 1 0 = 2

  
 
  • 1
  • 2
  • 3
  • 4

and运算通常用于二进制的取位操作。
小技巧:一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶,二进制的最末位为0表示该数为偶数,最末位为1表示该数为奇数。

更多技巧慢慢看,在后面。

按位或 |

相同位只要一个为1即为1。

示例:6 | 11

	0 1 1 0
	1 0 1 1
| ----------- 
	1 1 1 1 = 15

  
 
  • 1
  • 2
  • 3
  • 4

or运算通常用于二进制特定位上的无条件赋值。
小技巧:一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0,对这个数or 1之后再减一就可以了,其实际意义就是把这个数强行变成最接近的偶数。

更多技巧慢慢看,在后面。

按位异或 ^

两个位相同为0,相异为1

示例:6 ^ 11

	0 1 1 0
	1 0 1 1
^ -----------
	1 1 0 1 = 13

  
 
  • 1
  • 2
  • 3
  • 4

^运算通常用于翻转指定位。
小技巧:将数 X=1010 1110 的低4位进行翻转,只需要另找一个数Y,令Y的低4位为1,其余位为0,即Y=0000 1111,然后将X与Y进行异或运算(X^Y=1010 0001)即可得到。

更多技巧慢慢看,在后面。

按位取反

not运算的定义是把内存中的0和1全部取反。

示例:~ 6

使用按位取反运算符,要知道几点:
1、内存中,一个int,4个字节,1字节8位。
2、有符号整数的按位取反情况略有偏差。

	00000000 00000000 00000000 00000110
~ --------------------------
	11111111 11111111 11111111 11111001

  
 
  • 1
  • 2
  • 3

小技巧:可以用~使每个数的最低位为0,方法:a & ~1

别问我上面为什么不用这么长,我也不知道。我猜,是我不想写这么长哈哈哈。

左移位运算符 <<

将一个运算对象的各二进制位全部左移若干位(左边的二进制位丢弃,右边补0)。

示例:6 << 2

		0 1 1 0
<<2 ------------
	0 1 1 0 0 0 = 24

  
 
  • 1
  • 2
  • 3

小技巧:若左移时舍弃的高位不包含1,则每左移一位,相当于该数乘以2。

右移位运算符 >>

将一个数的各二进制位全部右移若干位,正数左补0,负数左补1,右边丢弃。

示例: 6 >> 2

		0 1 1 0
>>2 -------------
		0 0 0 1 = 1

  
 
  • 1
  • 2
  • 3

小技巧:操作数每右移一位,相当于该数除以2。

负数的二进制表示

既然都讲到这里了,那自然要了解一下负数的表示形式了。

==用字节的最高位表bai示:“1"表示"正”,“0"表示"负” ==

1、把补码“取反”(把二进制数的各位“1”换“0”,“0”换“1”。比如“101010”取反后为“010101”)
2、把取反后的二进制数“加1”

示例:-17 转码
再转回来

-17转码:

1700000000 00000000 00000000 00010001
反码:	11111111 11111111 11111111 11101110
转码:	11111111 11111111 11111111 11101111

  
 
  • 1
  • 2
  • 3

转回来自己动手。

所以C++中int的取值范围为:-2^31~2^31-1


投机

异或的几条性质

1、交换律
2、结合律(即(a^b)^c == a^(b^c)3、对于任何数x,都有x^x=0,x^0=x
4、自反性:  a^b^b=a^0=a;

  
 
  • 1
  • 2
  • 3
  • 4

位运算实现乘除

上面有

位运算实现swap

//普通操作
void swap(int &a, int &b) {
  a = a + b;
  b = a - b;
  a = a - b;
}

//位与操作
void swap(int &a, int &b) {
  a ^= b;
  b ^= a;
  a ^= b;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

呐,我来试试分析:

a ^= b  -->  a = a^b
b ^= a  -->  b = b^a^b = a
a ^= b  -->  a = a^b^a = b

  
 
  • 1
  • 2
  • 3

挺秀的啊,不过有的人说这样会出问题,比方说 a = b 的时候。
那我再来分析一下:

a ^= b  -->  a = a^b = 0
b ^= a  -->  b = b^a^b = a = 0
a ^= b  -->  a = a^b^a = b = 0

  
 
  • 1
  • 2
  • 3

哦,确实,他是对的。
都说是投机了,大家看着用吧,下面的其他投机技巧也说不定会是地雷哦。

位操作判断奇偶数

只要根据数的最后一位是 0 还是 1 来决定即可,为 0 就是偶数,为 1 就是奇数。

if(0 == (a & 1)) {
 //偶数
}

  
 
  • 1
  • 2
  • 3

位操作交换符号交换符号

将正数变成负数,负数变成正数

int reversal(int a) {
	return ~a + 1;
}

  
 
  • 1
  • 2
  • 3

整数取反加1,正好变成其对应的负数(补码表示);负数取反加一,则变为其原码,即正数5. 位操作求绝对值整数的绝对值是其本身,负数的绝对值正好可以对其进行取反加一求得,即我们首先判断其符号位(整数右移 31 位得到 0,负数右移 31 位得到 -1,即 0xffffffff),然后根据符号进行相应的操作

int abs(int a) {
	int i = a >> 31;
	return i == 0 ? a : (~a + 1);
}

  
 
  • 1
  • 2
  • 3
  • 4

上面的操作可以进行优化,可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况,即 i = 0 为正,i = -1 为负。对于任何数与 0 异或都会保持不变,与 -1 即 0xffffffff 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i),即整数时 a 与 0 异或得到本身,再减去 0,负数时与 0xffffffff 异或将 a 进行取反,然后在加上 1,即减去 i(i =-1)

int abs2(int a) { int i = a >> 31; return ((a^i) - i);
}

  
 
  • 1
  • 2
  • 3
  • 4

位操作统计二进制中 1 的个数

统计二进制1的个数可以分别获取每个二进制位数,然后再统计其1的个数,此方法效率比较低。这里介绍另外一种高效的方法,同样以 34520 为例,我们计算其 a &= (a-1)的结果:

第一次:计算前:1000 0110 1101 1000 计算后:1000 0110 1101 0000
第二次:计算前:1000 0110 1101 0000 计算后:1000 0110 1100 0000
第三次:计算前:1000 0110 1100 0000 计算后:1000 0110 1000 0000 

  
 
  • 1
  • 2
  • 3

我们发现,没计算一次二进制中就少了一个 1,则我们可以通过下面方法去统计:count = 0

while(a){ a = a & (a - 1); count++;  
}

  
 
  • 1
  • 2
  • 3
  • 4

用 O(1) 时间检测整数 n 是否是 2 的幂次

N如果是2的幂次,则N满足两个条件。

1.N >0
2.N的二进制表示中只有一个1

  
 
  • 1
  • 2

因为N的二进制表示中只有一个1,所以使用N & (N - 1)将N唯一的一个1消去,应该返回0。

数组中,只有一个数出现一次,剩下都出现两次,找出出现一次的数

因为只有一个数恰好出现一个,剩下的都出现过两次,所以只要将所有的数异或起来,就可以得到唯一的那个数。(异或自反性)

但当涉猎

1
a&a=a
a^a=0

2
a&0=0
a|0=a
a^0=a

3
a|(a&b)=a
a&(a|b)=a

4、交换值
a^=b;
b^=a;
a^=b;

5、判断奇偶(取出最后一位)
a &1
等价于a%2(结果等于,位运算效率高)

6、比较两值是否相等
a^b==0

7、i+1位置1
a |=1<<i

8、i+1位置0
a &=~(1<<i)

9、取出i+1(联系第5)
a & (1<<i)

10、在对应i+1位,插入b的对应位;
a |=1<<i; (a的bit位置1)
a & (b & 1<<i) (与b的bit位相与)

11、删除最后的1;
a & (a-1)

12、负数
a = ~a+1

13、仅保留最后一-1
a&(-a)

14、得到全1
~0

15、保留最后i-1位
a & ((1<<i)-1)

16、清零最后i-1位
a & ~((1<<i)-1)


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

以上,为最常见的用法,不带循环,全部O(1)。

这个要常回来看看啊。

一个大数去重的栗子

如何对10亿个QQ号进行去重


初次见面,先打基础,待我这两天去LeetCode上包装一下。
待我包装完,试试看用位运算进行排序能不能写出来。

位图

不急。。

过两天就写,估计也会是粉丝可见咯

文章来源: lion-wu.blog.csdn.net,作者:看,未来,版权归原作者所有,如需转载,请联系作者。

原文链接:lion-wu.blog.csdn.net/article/details/107244177

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。