位运算
博客专区 > 光斑 的博客 > 博客详情
位运算
光斑 发表于3个月前
位运算
  • 发表于 3个月前
  • 阅读 11
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

比如,and运算本来是一个逻辑运算符,但整数与整数之间也可以进行and运算。

举个例子,6的二进制是110,11的二进制是1011,那么6 and 11的结果就是2,它是二进制对应位进行逻辑运算的结果(0表示False,1表示True,空位都当0处理)。

        0110

    & 1011

---------------

         0010        --> 2

有人会说,计算6 and 11没有什么实际意义啊。这一系列的文章就将告诉你,位运算到底可以干什么,有些什么经典应用,以及如何用位运算优化你的程序

 

逻辑运算

 逻辑变量之间的运算称为逻辑运算二进制数1和0在逻辑上可以代表“真”与“假”、“是”与“否”、“有”与“无”。这种具有逻辑属性的变量就称为逻辑变量。 计算机的逻辑运算的算术运算的主要区别是:逻辑运算是按位进行的,位与位之间不像加减运算那样有进位或借位的联系。

逻辑运算主要包括三种基本运算:

逻辑乘法(又称“与”运算)、

逻辑加法(又称“或”运算)、

逻辑否定(又称“非”运算)。

运算符号

下面的a和b都是整数类型,则:

含义 Pascal语言 C语言 Java
按位与 a and b a & b a & b
按位或 a or b a | b a | b
按位异或 a xor b a ^ b a ^ b
按位取反 not a ~a ~a
左移 a shl b a << b a << b
带符号右移 a shr b a >> b a >> b
无符号右移     a>>> b

位运算

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了,就是直接对整数在内存中的二进制位进行操作

1.按位与&

  两位全为1,结果才为1. 例:0&1=0 1&1=1

  作用:

  1.清零

       2.一个数中指定数:

例:X=10101110 取X得低四位。 X&00001111=0000 1110

2.按位或 |

 只要有一个位1,结果就位1.

 作用:常用来对一个数据的某些位   置1.

 例:X=00001001 使X低四位为1。X|0000 1111=00001111

3.异或运算^

 两个相应位为"异"(值不同),则该位结果为1,否则为0.

   异或0具有保持的特点,而异或1具有翻转的特点

 作用:

          1.使特定位翻转,找一个数,对应X要翻转的各位,该数的对应位为1,其余位为0,此数与X对应位 异或即可。

        例:X=10101110 使X低四位翻转

     X^0000 1111=10100001

   2.与0相异或,保留自身原值。(应用在两个变量交换值,效率最高)

   例:A=A^B,B=A^B,A=A^B 这样A和B的值就交换了。

4.取反运算~

对一个二进制数按位取反。~0=1

   例:在java中对有符号int型数取反运算。

          注:在java中有符号整数都是用补码表示的

  所以我们还需要了解补码的知识:

    原码一个整数按照绝对值大小转换成的二进制数称为原码

    反码

    1.正数的反码与其原码相同

    2.负数的反码对其原码逐位取反,但符号位除外

    原码10010= 反码11101 (10010,1为符号码,故为

    (11101) 二进制

              原码:10010  = -2 十进制

    补码

    1.正数的补码与其原码相同

              2.负数的补码是在其反码的末位加1

                 取反方法:

                 1)对正数先对其表示的二进制取反,得到负数的补码;然后求出反码,最后求出原码。(即为所求数)

     例:~3

        java中int类型的长度是四个字节,也就是32位,so:

         00000000 00000000 00000000 00000011 

        取反:     1...                                         11111100  最高位为1,所以这是负数的补码形式。

        求出反码: 1...                                         11111011

                 求出原码:   0...                                         00000100  数字为4

        之前此数的补码最高位为1,所以 ~3=-4

     2)对负数:先求负数的补码,然后直接取反。(注意最高位1代表负数,0代表整数)。

 

 

  Java位运算是针对于整型数据类型的二进制进行的移位操作。主要包括位与、位或、位非,有符号左移、有符号右移,无符号右移等等。需要注意一点的是,不存在符号移<<<运算符。根据位运算的概念规定,我们首先需要弄明白两个问题,java有哪些数据类型是整型数据类型和各数字进制之间转换问题。Java整型数据类型有:byte、char、short、int、long。要把它们转换成二进制的原码形式,必须明白他们各占几个字节。我们都知道,一个字节占8位。
 

数据类型 所占位数
boolean 8
byte 8
short 16
char   16
int  32
long 64
float 32
double 64

下面根据实例一个一个的来说明各种位运算的运算规则:
位与&(真真为真 真假为假 假假为假)
4&6
0000 0000 0000 0000 0000 0000 0000 0100
0000 0000 0000 0000 0000 0000 0000 0110
0000 0000 0000 0000 0000 0000 0000 0100
结果:4

位或|(真真为真 真假为真 假假为假)
4|6
0000 0000 0000 0000 0000 0000 0000 0100
0000 0000 0000 0000 0000 0000 0000 0110
0000 0000 0000 0000 0000 0000 0000 0110
结果:6

位非~(取反码)【注:Java中正数的最高位为0,负数最高位为1,即最高位决定正负符号】
~4
0000 0000 0000 0000 0000 0000 0000 0100    ① 对4的原码取反
1111 1111 1111 1111 1111 1111 1111 1011    ②负数的补码

1111 1111 1111 1111 1111 1111 1111 1010     ③负数的补码-1 = 反码 
1000 0000 0000 0000 0000 0000 0000 0101      ④原码=反码 逐位取反 符号位不变
结果:-5

位异或^(真真为假 真假为真 假假为假)
4^6
0000 0000 0000 0000 0000 0000 0000 0100
0000 0000 0000 0000 0000 0000 0000 0110
0000 0000 0000 0000 0000 0000 0000 0010
结果:2

有符号右移>>(若正数,高位补0,负数,高位补1)
-4>>2

1000 0000 0000 0000 0000 0000 0000 0100   负数-4的补码(java中有符号整数都是用补码表示

1000 0000 0000 0000 0000 0000 0000 0011   反码 =  负数-4的补码 - 1
1111 1111 1111 1111 1111 1111 1111 1100   原码   逐位取反 符号位不变


1111 1111 1111 1111 1111 1111 1111 1111   右移,最左边空出两位按规则负数空位补1    
1000 0000 0000 0000 0000 0000 0000 0000   反码
1000 0000 0000 0000 0000 0000 0000 0001   补码(补码即最后一位+1)
结果:-1


有符号左移<<(若正数,高位补0,负数,高位补1)
-4<<2
1111 1111 1111 1111 1111 1111 1111 1100   原码
1111 1111 1111 1111 1111 1111 1111 0000   左移,最右边空出两位补0
0000 0000 0000 0000 0000 0000 0000 1111   解码
0000 0000 0000 0000 0000 0000 0001 0000   补码
结果:-16

无符号右移>>>(不论正负,高位均补0)
-4>>>2
1111 1111 1111 1111 1111 1111 1111 1100   原码
0011 1111 1111 1111 1111 1111 1111 1111   右移(由于高位均补0,故>>>后的结果一定是正数)
结果:1073741823

 

由于数据类型所占字节是有限的,而位移的大小却可以任意大小,所以可能存在位移后超过了该数据类型的表示范围,于是有了这样的规定:
如果为int数据类型,且位移位数大于32位,则首先把位移位数对32取模,不然位移超过总位数没意义的。所以4>>32与4>>0是等价的。

如果为long类型,且位移位数大于64位,则首先把位移位数对64取模,若没超过64位则不用对位数取模。

如果为byte、char、short,则会首先将他们扩充到32位,然后的规则就按照int类型来处理。

 

学到这里,我想你也可能会问,位运算到底有什么用途或者有哪些场景可以应用到它。因为位运算的运算效率比直接对数字进行加减乘除高很多,所以当出现以下情景且对运算效率要求较高时,可以考虑使用位运算。不过实际工作中,很少用到它,我也不知道为什么很少有人用它,我想应该是它比较晦涩难懂,如果用它来进行一些运算,估计编写的代码的可读性会不强,毕竟我们写的代码不仅仅留给自己一个人看。
1.  判断int型变量a是奇数还是偶数    
     a&1  = 0 偶数 
     a&1 =  1 奇数 
2.  求平均值,比如有两个int类型变量x、y,首先要求x+y的和,再除以2,但是有可能x+y的结果会超过int的最大表示范围,所以位运算就派上用场啦。
      (x&y)+((x^y)>>1); 
3.  对于一个大于0的整数,判断它是不是2的几次方
    ((x&(x-1))==0)&&(x!=0); 
4.  比如有两个int类型变量x、y,要求两者数字交换,位运算的实现方法:性能绝对高效
    x ^= y; 
    y ^= x; 
    x ^= y; 
5. 求绝对值
    int abs( int x ) 
   { 
     int y ; 
     y = x >> 31 ; 
    return (x^y)-y ;        //or: (x+y)^y 
   }
6.  取模运算,采用位运算实现:
     a % (2^n) 等价于 a & (2^n - 1) 
7.  乘法运算   采用位运算实现
     a * (2^n) 等价于 a << n
8.   除法运算转化成位运算
      a / (2^n) 等价于 a>> n 
9.   求相反数
      (~x+1) 
10  a % 2 等价于 a & 1 

等等
当然还有牛人使用位运算来实现权限控制,加密技术,里面的奥秘深不可测啊!哈哈。

 

优秀程序员不得不知道的20个位运算技巧

干货!史上最强位运算面试题大总结!

  • 点赞
  • 收藏
  • 分享
粉丝 6
博文 146
码字总数 138938