一文读懂位运算

2021-09-26

概述

在计算机程序中所有的数都是以二进制形式存储的。位运算就是直接对整数在二进制进行计算操作。作为一名程序员掌握位运算的基本使用是很重要的,而对于算法程序员来说,位运算的灵活使用能够更灵活高效的解决很多问题。

位运算都有哪些

符号 描述 运算规则
& 同为1时结果为1,其它为0
| 同为0时结果为0,其它为1
^ 异或 相同为0,不同为1
~ 取反 0变1,1变0
<< 左移 各位左移,高位丢弃,低位补0
>> 右移 各位右移,低位丢弃,如果该数为正则高位补0;反之补1
>>> 无符号右移 又称逻辑右移,不管正负,高位补0

运算符逻辑

按为与(&)

参加运算的两个数按二进制进行与运算。

0&0=0
0&1=0
1&1=1

用途:

清零

任何数与0做与运算结果都为0。

取指定位

比如要取一个数的低4位,则只需使用该数与(0000 1111)做与运行,结果就是这个数的低4位的值。

奇偶判断

只要二进制的末尾为0则是偶数,为1则为奇数。因此可用 (x&1)==0判断是否是偶数。

按位或(|)

参加运算的两个数按二进制进行或运算。

0|0=0
0|1=1
1|1=1

用途:

将某位设置为1

如X=0101,需要将第2位设置为1,结果变为0111,则只需和(0010)进行或运算,0101|0010=0111。

按位异或(^)

参加运算的两个数按二进制进行异或运算。

0^0=0
0^1=1
1^1=0

用途:

翻转指定位

如要将X=0101 1010的低4位翻转为0101,则只需和Y=0000 1111进行异或运行,X^Y=0101 0101 。

交换两数值

如X=0101,Y=0100,需要将X和Y的值进行交换。

x ^= y; // x= 0101 ^ 0100  = 0001
y ^= x; // y = 0100 ^ 0001 = 0101
x ^= y; // x = 0001 ^ 0101 = 0100

按位取反(~)

参加运算的1个数据各位值0变1,1变0.

~0101=1010

用途:

取反运算和用于快速获得某个特定值,如获取一个最低位为0其他位为1的数,则对1进行取反即可,~1。

左移运算符(<<)

参与运算的1个数据各位左移,高位丢弃,低位补0。

0101 << 1 = 1010

如果左移的数最高位不等于1,则相当于乘2。

右移运算符(>>)

参与运算的1个数据各位右移,如果该数为正则高位补0,反之补1,低位丢弃。

0101 >> 1 = 0010

某数进行右移运算相当于除以2。

无符号右移运算符(>>>)

又称逻辑右移,不管正负,高位补0。

0101>>>1=0010

如负数-5进行右移操作,结果如下。(-5的二进制表示为11111111111111111111111111111011)

11111111111111111111111111111011>>>1=01111111111111111111111111111101

注:负数的二进制表示形式为补码。

有哪些骚操作

技巧一

x & (x - 1) 用于消去x最后一位的1

应用:检测整数x是否是2的次幂

思路:2的次幂满足以下条件:

  1. 大于0
  2. 只有1个位是1

则x & (x - 1)的结果如果等于0则表示x是2的次幂。

技巧二

a ^ b ^ b = a

一个数据集合中,只有1个数字出现1次,其他数字都出现两次,找出这个数。

思路:只需要将所有数据进行异或运算,结果就是这个数。

一个数据集合中,只有2个数字出现过1次,其他数字都出现过两次,找出这两个数。

思路:假设这两个数是X,Y,所有数字进行异或的结果就是X^Y,因为异或运算逻辑是相同为0,不同为1,则找出这个结果的二进制中等于1的位置,然后将所有数字按照该位是否为1分成两部分,那么X和Y会被分开,然后分别做异或运算,结果便是X和Y.

小结

位运算在各大互联网公司的面经中经常会出现,各种算法题中也高频使用,希望本文能让你对位运算有一个初步的认识。

来都来了,点个赞再走啦~