彻底搞清楚Java的位运算（位实现加减乘除）

﹏ヽ暗。殇╰゛Y 2023-06-24 13:28 1阅读 0赞

**目录**

•写在前面

•机器数和机器数的真值

•原码、反码和补码的基础概念和计算方法

原码

反码

补码

•java中的运算符

•不用乘除算乘除

加法

减法

乘法

除法

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

# •写在前面 #

二进制位运算是最贴近计算机真实运算操作，通过位运算，我们可以高效的完成各种基础运算（加减乘除取余等），我们还可以使用位运算巧妙的完成原本很复杂的工作，真正理解计算机，我们才能更好的使用计算机。在这一片文章，我将通过基础理解开始，讲解到Java中的一些实际应用。

# •机器数和机器数的真值 #

一个数在计算机中的二进制表示形式，叫做这个数的机器数。机器数是带符号的，在计算机用机器数的最高位存放符号，正数为0，负数为1。举个例子，比如在机器字长为8位的情况下（机器字长是指计算机直接处理的二进制数据的位数，它决定了计算机的运算精度，一般是8的整数倍，8位、16位、32位、64位、128位），十进制中的+3，转换成二进制就是0000 0011，如果是-3，转换成二进制就是1000 0011。转换的二进制数0000 0011和1000 0011就是机器数。

这里我们还需要知道的就是机器数的真值，由于机器数的第一位是符号位，所以机器数的形式值就不等于真正的数值。例如上面的有符号数1000 0011，其最高位1代表负，其真正数值是-3，而不是形式值131（1000 0011转换成十进制等于131），所以，为了区别起见，将带符号的机器数对应的真正数值成为机器数的真值。比如0000 0001的真值 = +000 0001 = +1，1000 0001的真值 = –000 0001 = –1

# •原码、反码和补码的基础概念和计算方法 #

上面我们了解了机器数，也就是二进制数，不过计算机要使用一定的编码方法进行储存，原码、反码和补码就是机器存储一个具体数字的编码方式。

## 原码 ##

原码就是符号位加上真值的绝对值，即用第一位表示符号，其余位表示值，比如：如果8位二进制：

\[+1\]原= 0000 0001

\[-1\]原= 1000 0001

第一位是符号位，因为第一位是符号位，所以8位二进制数的取值范围就是：（即第一位不表示值，只表示正负。）\[1111 1111 , 0111 1111\]，也就是十进制的\[-127 , 127\]（小声哔哔，其实可以说成原码是带符号的机器数）。

## 反码 ##

正数的反码就是其本身，负数的反码是其原码的基础上，符号位不变，其余各个位取反。

\[+1\] = \[0000 0001\]原= \[0000 0001\]反

\[-1\] = \[1000 0001\]原= \[1111 1110\]反

## 补码 ##

补码的表示方法是，正数的补码就是其本身，负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后+1（也就是在其反码的基础上+1）

\[+1\] = \[0000 0001\]原= \[0000 0001\]反= \[0000 0001\]补

\[-1\] = \[1000 0001\]原= \[1111 1110\]反= \[1111 1111\]补

知道了这三个基本概念之后，值得一提的是，如果用反码相加，会产生两个零的问题（-0和+0），所以我们使用补码，不仅仅修复了0的符号以及存在两个编码的问题，而且还能够多表示一个最低数。这就是为什么8位二进制，使用原码或反码表示的范围为\[-127, +127\]，而使用补码表示的范围为\[-128, 127\]。因为机器使用补码，所以对于编程中常用到的有符号的32位int类型，可以表示范围是: \[-231, 231-1\] 因为第一位表示的是符号位，而使用补码表示时又可以多保存一个最小值。

# •java中的运算符 #

**注意了，以下所有的位运算都是通过补码进行的，正数的补码就是它本身，负数自己对应算，两个操作数都为正数，则结果直接取二进制转十进制，如果两个操作数其中有一个是负数或者两个都为负数，则结果如果符号位是1（即负的），则得到的是补码，需要从补码转到原码，再转换成十进制，如果结果符号位是0，直接取二进制转十进制。也就是运算时逢负取补，结果是逢负取原。**可以自己先把下面十进制数全部转换成二进制补码，然后带进去算，看一下是不是正确结果。

异或运算符号是“^”，相同的为0，不同的为1，代码举例如下：

public static void main(String[] args) {
        System.out.println("2^3运算的结果是 :"+(2^3));
        //打印的结果是:   2^3运算的结果是 :1
    }
    
    //2的二进制0010，3的二进制0011，2^3就为0001，结果就是1
    
    public static void main(String[] args) {
        System.out.println("-2^3运算的结果是 :"+(-2^3));
        //打印的结果是:   -2^3运算的结果是 :-3
    }
    
    //-2的二进制补码1110，3的二进制0011，-2^3就为0001，结果就是-3

与运算符号是“&”，只要有一个为0就为0，代码举例如下：

public static void main(String[] args) {
         System.out.println("2&3运算的结果是 :"+(2&3));
         //打印的结果是:   2&3运算的结果是 :2
    }
    
    public static void main(String[] args) {
         System.out.println("-2&3运算的结果是 :"+(-2&3));
         //打印的结果是:   -2&3运算的结果是 :2
    }

或运算符是“|”，只要有一个为1就是1，代码举例如下：

public static void main(String[] args){
        System.out.println("2|3运算的结果是 ："+(2|3));
        //打印的结果是： 2|3运算的结果是 ： 3
    }
    
    public static void main(String[] args){
        System.out.println("-2|3运算的结果是 ："+(-2|3));
        //打印的结果是： -2|3运算的结果是 ： -1
    }

非运算符是“~”，就是各位取反，代码举例如下：

public static void main(String[] args){
        System.out.println("~5运算的结果是 ："+(~5));
        //打印的结果是： ~5运算的结果是 ： -6
    }
    
    public static void main(String[] args){
        System.out.println("~(-5)运算的结果是 ："+(~(-5)));
        //打印的结果是： ~(-5)运算的结果是 ： 4
    }

向左位移符号“<<，二进制向左移动n位，后面用0补齐

public static void main(String[] args) {
         System.out.println("2<<3运算的结果是 :"+(2<<3));
         //打印的结果是:   2<<3运算的意思是，向左移动3位，其结果是 :16
    }
    
    public static void main(String[] args) {
         System.out.println("-2<<3运算的结果是 :"+(-2<<3));
         //打印的结果是:   -2<<3运算的意思是，向左移动3位，其结果是 :-16
    }

向右位移符号“>>”，二进制向右移动n位，若值为正，则在高位插入 0，若值为负，则在高位插入 1。

public static void main(String[] args) {
         System.out.println("2>>3运算的结果是 :"+(2>>3));
         //打印的结果是:   2>>3运算的意思是，向右移动3位，其结果是 :0
    }
    
    public static void main(String[] args) {
         System.out.println("-2>>3运算的结果是 :"+(-2>>3));
         //打印的结果是:   -2>>3运算的意思是，向右移动3位，其结果是 :-1
    }

无符号右移符号“>>>”，忽略符号位，空位都以0补齐。>>>与>>唯一的不同是它无论原来的最左边是什么数，统统都用0填充。比如，byte是8位的，-1表示为byte型是11111111(补码表示法） b>>>4就是无符号右移4位，即00001111，这样结果就是15。(小声哔哔，别问我有没有无符号左移，等你真正融会贯通之后，你会发现这是一个很low的问题。）

public static void main(String[] args) {
         System.out.println("16>>2运算的结果是 :"+((16)>>2));
         //打印的结果是:   16>>2运算的结果是 :4
    }
    public static void main(String[] args) {
         System.out.println("-16>>2运算的结果是 :"+((-16)>>2));
         //打印的结果是:   -16>>2运算的结果是 :-4
    }
    
    public static void main(String[] args) {
         System.out.println("16>>>2运算的结果是 :"+((16)>>>2));
         //打印的结果是:   16>>>2运算的结果是 :4
    }
    
    public static void main(String[] args) {
         System.out.println("-16>>>2运算的结果是 :"+((-16)>>>2));
         //打印的结果是:   -16>>>2运算的结果是 :1073741820
    }

# •不用乘除算乘除 #

## 加法 ##

以13+9为例，我们像这样来拆分这个运算过程：

*  步骤一：不考虑进位，分别对各位数进行相加，结果为存为sum，个位数3加上9为2；十位数1加上0为1； 最终结果为12；
 *  步骤二：只考虑进位，结果存为carry，3 + 9 有进位，进位的值为10；
 *  步骤三：如果步骤二所得进位结果carry不为0，对步骤一所得sum以及步骤二所得carry，重复步骤一、二、三。如果carry为0则结束，最终结果为步骤一所得sum。

这里其实就是对sum = 12 和carry = 10重复以上三个步骤，

*  (a) 不考虑进位，分别对各位数进行相加，sum = 22;
 *  (b) 只考虑进位: 上一步没有进位，所以carry = 0； (c) 步骤2carry = 0，结束，结果为sum = 22.

这是我们在十进制中进行的运算演示，那我们换成二进制看看是不是一样，13的二进制为0000 1101，9的二进制为0000 1001:

*  第一步：不考虑进位，分别对各位数进行相加，sum = 0000 1101 + 0000 1001 = 0000 0100
 *  第二步：考虑进位， 有两处进位，第0位和第3位，只考虑进位的结果为： carry = 0001 0010
 *  第三步：carry == 0 ?，不为0，重复步骤一 、二 、三；为0则结束，结果为sum。

本例中，

*  (a)不考虑进位sum = 0001 0110; 
 *  (b)只考虑进位carry = 0; 
 *  (c)carry == 0，结束，结果为sum = 0001 0110

转换成十进制刚好是22.

其实就是三个步骤，用形象的伪代码来理解如下，这次用3+9举例。

a = 0011, b = 1001;
        start;
    
        first loop;
        1.1 sum = 1010
        1.2 carry = 0010
        1.3 carry != 0 , go on;
    
        second loop;
        2.1 sum = 1000;
        2.2 carry = 0100;
        2.3 carry != 0, go on;
    
        third loop;
        3.1 sum = 1100;
        3.2 carry = 0000;
        3.3 carry == 0, stop; result = sum;
    
    end

//1、递归形式实现
    int add(int a ,int b){
        if (b == 0)
            return a;
        else{
            int carry = (a & b) << 1;
            a = a ^b;
            return add(a,carry);
        }
    }
     
    //非递归形式实现
    int add2(int a ,int b){
       int carry;
       while (b != 0){
       carry = (a & b) << 1;
           a = a ^b;
           b = carry;
       }
       return a;
    }

## 减法 ##

我们知道了位运算实现加法运算，那减法运算就相对简单一些了。我们实现了加法运算，自然的，我们会想到把减法运算11 - 6变形为加法运算11 + (-6)，即一个正数加上一个负数。是的，很聪明，其实我们的计算机也是这样操作的，那有的人会说为什么计算机不也像加法器一样实现一个减法器呢？对的，这样想当然是合理的，但是考虑到减法比加法来的复杂，实现起来比较困难。为什么呢？我们知道加法运算其实只有两个操作，加、 进位，而减法呢，减法会有借位操作，如果当前位不够减那就从高位借位来做减法，这里就会问题了，借位怎么表示呢？加法运算中，进位通过与运算并左移一位实现，而借位就真的不好表示了。所以我们自然的想到将减法运算转变成加法运算。怎么实现呢？

刚刚我们说了减法运算可转变成一个正数加上一个负数，那首先就要来看看负数在计算机中是怎么表示的。

\+8在计算机中表示为二进制的1000，那-8怎么表示呢？很容易想到，可以将一个二进制位（bit）专门规定为符号位，它等于0时就表示正数，等于1时就表示负数。比如，在8位机中，规定每个字节的最高位为符号位。那么，+8就是00001000，而-8则是10001000。这只是直观的表示方法，其实计算机是通过2的补码来表示负数的，那什么是2的补码（同补码，英文是2’s complement，其实应该翻译为2的补码）呢？它是一种用二进制表示有号数的方法，也是一种将数字的正负号变号的方式，求取步骤：

*  第一步，每一个二进制位都取相反值，0变成1，1变成0（即反码）。
 *  第二步，将上一步得到的值（反码）加1。

简单来说就是取反加一！

int subtraction(int a ,int b){
             b = ~b+1;
             return this.add(a,b);
         }

## 乘法 ##

考虑我们现实生活中手动求乘积的过程，这种方式同样适用于二进制，下面我以13\*14为例，向大家演示如何用手动计算的方式求乘数和被乘数绝对值的乘积。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70][]

从上图的计算过程可以看出，如果乘数当前位为1，则取被乘数左移一位的结果加到最终结果中；如果当前位为0，则取0加到乘积中（加0也就是什么也不做）

*  (1) 判断乘数是否为0，为0跳转至步骤(4)
 *  (2) 将乘数与1作与运算，确定末尾位为1还是为0，如果为1，则相加数为当前被乘数；如果为0，则相加数为0；将相加数加到最终结果中；
 *  (3) 被乘数左移一位，乘数右移一位；回到步骤(1)
 *  (4) 确定符号位，输出结果；

//a 被乘数，b 乘数
          int multiplication(int a,int b){
              int i = 0;
              int res = 0;
              //乘数不为0
              while (b != 0){
                  //处理当前位
                  //当前位是1
                 if ((b & 1) == 1){
                     res += (a << i);
                     b = b >> 1;
                     //记录当前是第几位
                     i++;
                 }else {
                     //当前位是0
                     b = b >> 1;
                     i++;
                 }
             }
             return res;
         }

## 除法 ##

除法运算很容易想到可以转换成减法运算，即不停的用除数去减被除数，直到被除数小于除数时，此时所减的次数就是我们需要的商，而此时的被除数就是余数。这里需要注意的是符号的确定，商的符号和乘法运算中乘积的符号确定一样，即取决于除数和被除数，同号为证，异号为负；余数的符号和被除数一样。 计算机是一个二元的世界，所有的int型数据都可以用\[2^0, 2^1,…,2^31\]这样一组基来表示（int型最高31位）。不难想到用除数的2^31,2^30,…,2^2,2^1,2^0倍尝试去减被除数，如果减得动，则把相应的倍数加到商中；如果减不动，则依次尝试更小的倍数。这样就可以快速逼近最终的结果。

2的i次方其实就相当于左移i位，为什么从31位开始呢？因为int型数据最大值就是2^31啊。

int division(int a,int b){
              int res;
              if(a<b){
                  return 0;
              }else{
                  res=division(subtraction(a, b), b)+1;
              }
              return res;
         }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191223202004900.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE=,size_16,color_FFFFFF,t_70