位运算

时间：2024-01-30 12:39:34

 常见的运算符有与(&)、或(|)、异或(^)、取反(~)、左移(<<)、右移(>>是带符号右移 >>>无符号右移动)。下面来细看看每一种位运算的规则。

 

按位取反~

规则：二进制的0变成1，1变成0。

|=

public static strictfp void main(String[] args) {

   int a = 5; // 0000 0101
   int b = 3; // 0000 0011
   a |= b; // 0000 00111
   System.out.println(a);

}

具体规则为：两个二进制对应位为0时该位为0，否则为1。拿5的二进制 0000 0101 和 3的二进制 0000 0011 进行|运算，后三位的的对应位都不是同时等于0，所以最终结果为 0000 0111 也就是7的二进制。

&=

public static strictfp void main(String[] args) {

    int a = 5; // 0000 0101
    int b = 3; // 0000 0011
    a &= b; // 0000 0001
    System.out.println(a);
}

　　具体规则为：两个二进制对应位都为1时，结果为1，否则结果为都0。拿5的二进制 0000 0101 和 3的二进制 0000 0011 进行&运算，只有最后一位都为1，则最终结果为 0000 0001 也就是1的二进制。

^=

public static strictfp void main(String[] args) {
    int a = 5; // 0000 0101
    int b = 3; // 0000 0011
    a ^= b; // 0000 0110
    System.out.println(a);
}

具体规则为：两个二进制对应位相同时，结果为0，否则结果为1。拿5的二进制 0000 0101 和 3的二进制 0000 0011 进行^运算，1-5位对应位都是0所以1-5位都为0，第8位都为1所以第8位也为0，其他的对应位都不相等所以为1，则最终结果为 0000 0110 也就是6的二进制。

 

<<表示左移移，不分正负数，低位补0；　

注：以下数据类型默认为byte-8位

左移时不管正负，低位补0

正数：r = 20 << 2

　　20的二进制补码：0001 0100

　　向左移动两位后：0101 0000

　　　　   　　结果：r = 80

负数：r = -20 << 2

　　-20 的二进制原码 ：1001 0100

　　-20 的二进制反码 ：1110 1011

　　-20 的二进制补码 ：1110 1100

　　左移两位后的补码：1011 0000

　　　　　　　　反码：1010 1111

　　　　　　　　原码：1101 0000

　　　　　　　　结果：r = -80

>>表示右移，如果该数为正，则高位补0，若为负数，则高位补1；

注：以下数据类型默认为byte-8位

正数：r = 20 >> 2

　　20的二进制补码：0001 0100

　　向右移动两位后：0000 0101

　　　　　　　结果：r = 5

负数：r = -20 >> 2

　　-20 的二进制原码 ：1001 0100

　　-20 的二进制反码 ：1110 1011

　　-20 的二进制补码 ：1110 1100 

　　右移两位后的补码：1111 1011 

　　　　　　　　反码：1111 1010

　　　　　　　　原码：1000 0101

　　　　　　　　结果：r = -5

>>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0

正数：　r = 20 >>> 2

　　　　的结果与 r = 20 >> 2 相同；

负数：　r = -20 >>> 2

注：以下数据类型默认为int 32位

　　-20:源码：10000000 00000000 00000000 00010100

　　　　反码：11111111  11111111   11111111   11101011

　　　　补码：11111111  11111111   11111111   11101100

　　　　右移：00111111  11111111   11111111   11111011

　　　　结果：r = 1073741819

 

移位运算符

左移运算<<：左移后右边位补 0

右移运算>>：右移后左边位补原最左位值(可能是0，可能是1)

右移运算>>>：右移后左边位补 0

  • 对于左移运算符<<没有悬念右侧填个零无论正负数相当于整个数乘以2。

  • 而右移运算符就有分歧了，分别是左侧补0>>>和左侧补原始位>>，如果是正数没争议左侧都是补0，达到除以2的效果；如果是负数的话左侧补0>>>那么数值的正负会发生改变，会从一个负数变成一个相对较大的正数。而如果是左侧补原始位(负数补1)>>那么整个数还是负数，也就是相当于除以2的效果。

 

 

位运算小技巧

在这里有些常用的位运算小技巧。

判断奇偶数

正常判断奇数偶数的时候我们会这样写：

if( n % 2 == 1)
    // n 是个奇数
}

使用位运算可以这么写：

if(n & 1 == 1){
    // n 是个奇数。
}

其核心就是判断二进制的最后一位是否为1，如果为1那么结果加上2^0=1一定是个奇数，否则就是个偶数。

交换两个数

对于传统的交换两个数，我们需要使用一个变量来辅助完成操作，可能会是这样：

int team = a;
a = b;
b = team;

但是使用位运算可以不需要借助额外空间完成数值交换：

a=a^b;//a=a^b
b=a^b;//b=(a^b)^b=a^0=a
a=a^b;//a=(a^b)^(a^b^b)=0^b=0

原理已经写在注释里面了，是不是感觉非常diao呢？

二进制枚举

在遇到子集问题的处理时候，我们有时候会借助二进制枚举来遍历各种状态(效率大于dfs回溯)。这种就属于排列组合的问题了，对于每个物品(位置)来说，就是使用和不使用的两个状态，而在二进制中刚好可以用1和0来表示。而在实现上，通过枚举数字范围分析每个二进制数字各符号位上的特征进行计算求解操作即可。

二进制枚举的代码实现为：

for(int i = 0; i < (1<<n); i++) //从0～2^n-1个状态
{
  for(int j = 0; j < n; j++) //遍历二进制的每一位 共n位
  {
    if(i & (1 << j))//判断二进制数字i的第j位是否存在
    {
      //操作或者输出
    }
  }
}

位运算经典问题

有了上面的位运算基础，我们怎么用位运算处理实际问题呢？或者有哪些经典的问题可以用位运算来解决呢。

不用加减乘除做加法

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

分析：这道题咋一听可能没啥思路，简单研究一下位运算还是能独立推出来和理解的。

当然，解决这题前，需要了解上面的四种位运算。还要知道二进制的运算：0+0=0，0+1=1,1+1=0(进位)

对于加法的一个二进制运算。如果不进位那么就是非常容易的。这时候相同位都为0则为0，0和1则为1.满足这种运算的异或(不相同取1，相同取0)和或(有一个1则为1)都能满足.但事实肯定有进位的运算啊！看到上面操作的不足之后，我们肯定还需要解决进位的问题对于进位的两数相加，这种核心思想为：

  • 用两个数，一个正常m相加(不考虑进位的)。用异或a^b就是满足这种要求，先不考虑进位(如果没进位那么就是最终结果)。另一个专门考虑进位的n。两个1需要进位。所以我们用a&b与记录需要进位的。但是还有个问题，进位的要往上面进位，所以就变成这个需要进位的数左移一位。
  • 然后就变成m+n重新迭代开始上面直到不需要进位的(即n=0时候)。

 

实现代码为：

public class Solution {
     public int Add(int num1,int num2) {
  /*
   *  5+3   5^3(0110)   5&3(0001) 
   *  0101    
   *  0011 
   */
  int a=num1^num2;
  int b=num1&num2;
  b=b<<1;
  if(b==0)return a;
  else {
   return Add(a, b);
  }        
  }
}

当然，这里也可以科普一下二进制求加法：average = （a&b） + ((a^b)>>1) ;

 

 

参考：https://www.cnblogs.com/chuijingjing/p/9405598.html

　　https://www.cnblogs.com/qubaba/p/11558127.html

https://mp.weixin.qq.com/s/JIUG2PIwNK_ebzCTeeyYlQ    （更多可以参考）

相关文章