位运算介绍 & 应用

0
11

介绍

一、<< & >>

shl =  << (左移)    |    shr = >> (右移)
shl: 左移 <<
用来将一个数的各二进制位全部左移若干位,移动的位数由右操作数指定,右操作数必须是非负值,其右边空出的位用0填补,高位左移溢出则舍弃该高位
a << b = a* 2^b
shr: 右移 >>
右移运算是将一个二进制位的操作数按指定移动的位数向右移动,移出位被丢弃,左边移出的空位或者一律补0
a << b = a/ 2^b

二、and & or

and(&)(与)(∧)
都是1,取1

or(|)(或)(∨)
有1,就取1

xor(^)(异或)
相同为0,不同为1
10111 ^ 00101
= 10010

¬ 非 表示取反


应用

一、判断一个数字X的i位是不是1

方法:

  if((1 << (i-1)) & x > 0)
原理:
  1左移(i-1)位,相当于制造了一个就i位上是1其他位都是0的一个二进制数。将这个数与X进行“与”运算,如果大于0,则代表第i位是1;否则是0
例子:
  x = 13 (1101)2  i = 3
 ∴ 1 << (i-1) = 1 << 2 = 1002 = 01002 (补上0)
 ∴ (1<< (i-1)) & x
 = 01002 & 11012
 = 01002
  因为其0100大于0,所以这i位是1

二、把一个数字二进制下的第i位改成1

方法:

  x = x | (1 << (i-1))

原理:

  与“一”类似,直接看”例子“吧  

例子:

  x = 13 (1101)2  i = 2

 ∴ 1 << (i-1) = 1 << 1 = 102 = 00102

 ∴ x | (1 << (i-1))

 = 11012 | 00102

 = 11112

三、把一个数字二进制下的最靠右的第一个1改成0(去掉)

方法:

  x = x & (x-1)

原理:

  十进制下的数减了1后,二进制下的数最右边的1肯定会变成0,所以通过“与”一下就可以把最靠右的第一个1改成0

例子:

  x = 13 (1101)2

 ∴ x-1 = 12 = 11002

 ∴ x & (x-1)

 = 11012& 11002

 = 11002

四、返回二进制最低位1的权值

方法:

  x & (-x)

原理:

  -x 就是 x 的补码,会把x二进制各个位上的数字反转(1 变 0; 0 变 1)再加1

   ps: 多位数中,某一位上“i”的值表示该位的权制

    如 二进制中 第3位上是数字1, 则该位的权制就等于22 = 4

例子:(这里忽略符号位)

  x = 13(1101)2

  x & (-x) = 11012 + 00002 + 12= 110

  x = 26(11010)2

  x & (-x) =110102+ 001012 + 12= 110102+ 001102 =210

  x = 40(101000)2

  x & (-x) = 1010002+ 0101112+ 12= 1010002+ 0110002 =810

<

发布回复

请输入评论!
请输入你的名字