四则运算的移位实现，以及POW的实现

我就是我 2022-05-23 04:36 176阅读 0赞

# 位运算 #

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

## 一、位运算简介 ##

**  我们先来熟悉下位运算的操作，大致要用到的位运算如下**：

> 1.  `与(&)操作`，该操作先将数值转换为二进制（如：`a=3 => a=11`），然后再进行操作。会对两个数相同的位置上进行操作，如果两个操作数长度不一致，会对值较短的数进行高位补0。（如：`a =3 , b = 4, a+b = 011+100`）；相同位置为全1才为1，有0必为0，则上述结果：`a&b = 000`。
> 2.  `或(|)操作`，跟`与(&)操作`不一样的地方在于，相同位置有1则1。`a|b = 000`。
> 3.  `异或(^)操作`，相同则为0，不同则为1。`a^b = 111`。

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

我们将从加法开始依次分析。

## 二进制加法 ##

>   可以很轻松的利用`异或(^)操作`与`与(&)操作`来实现加法的运算。`与(&)操作`可以用来获取两者相加进位，因为相同的位置同时出现1结果才为1，那么此时对结果集进行`左移(<<)`操作得到即为进位的值，采用`异或(^)操作`得到的是我们不带进位的相加结果，再利用不带进位与进位相加，依次迭代，即可以求出我们需要的值。
> 
> --------------------
> 
> `例如：a=010010，b=100111`,计算步骤如下：

`代码清单 1.`

public int add(int sum1,int sum2){
        if(sum1 == 0) return sum2;
        if(sum2 == 0) return sum1;
        //这里sum代表结果集，carry代表的是进位
        int sum = 0,carry;
        while(sum2 != 0){
            //这里的num1^num2得到的正是两者相加，不带进位的结果
            //首轮结果 010010^100111 = 110101
            sum = num1^num2;
            //carry代表的进位 (010010&100111) <<1= (000010)<<1 = (000100),在这里刚好进位了
            carry = (num1&num2)<<1;
            //这里替换掉num1,num2是为了方便迭代，当carry为0,即无进位结束循环
            num1 = sum;
            sum2 = carry;
        }
        return sum;
    }

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

## 二进制减法 ##

>   二进制的减法跟简单，其实就是在加法的基础上进行改进，众所周知，在计算机中一切都是在做加法，减法的由来就是一个数加上另外一个数的负数。**`计算机中的负数`可以采用补码+1的形式得到**
> 
> --------------------
> 
> tip: `取反（~）`得到补码: a的补码为~a。

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

`代码清单 2.`

public int sub(int num1,int num2){
          return add(num1,add(~num2,1));
      }

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

## 二进制乘法 ##

>   乘法有个特性就是，当你乘一个数的时候，你会左移它所出现的位置步，比如：1011\*0010那么就会左移动1位，1011\*1000左移3位，利用好这个特性我们就可以对一个数进行拆分了，保留每一位上面的1，其余的都变成0。
> 
> --------------------
> 
> 在这里需要用到几个辅助的位操作：  
> `1. -n = ~(n-1) = ~n+1`  
> `2. n&~(n-1)`，获取n中二进制中的最后一个1  
> `3. n&(n-1)`，去掉n中二进制中的最后一个1

`代码清单3.`

public int multiply(int a,int b) {
            //利用map存放需要移动的位数，以及1向左移动i位的值
            //用于快速缓存移动的位数，将移位的值->移位位数进行mapping
            Map<Integer,Integer> map = new HashMap<>();
            for(int i=0;i<32;i++) {
                map.put(1<<i, i);
            }
            int sum = 0;
            while(b>0) { 
                int last = b&(~(b-1));//取得最后一个1;
                int count = map.get(last);//取得移动的位数
                sum = add(sum,a<<count);
                b = b&(b-1); //去掉最后一个1;
            }
            return sum;
        }

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

## 二进制除法 ##

>   二进制的除法可以利用移位跟加减法进行计算。思路如下：先对除数进行移位操作，移位到一个临界值，即比被除数小的最大值，再用除数进行迭代相减，有点类似辗转相除法。

`代码清代4.`

public int div(int a,int b) {
            if(a<b) {
                return 0;
            }
            int bleft = 0; //b左移的位数
            //迭代获取除数达到临界值需要移动的位数
            while((bleft <<msb)<a) {
                bleft ++;
            }
            int res = 0;//商
            for(int i=bleft ;i>=0;i--) {
            //每次进行检验，如果当除数移位后，大于被除数，跳过这次循环
                if((b<<i)>a) continue;
                //这里记录移位的结果集，当i满足的时候即为1不满足即为0
                res |= (1<<i);
                //缩小被除数的范围。
                a = sub(a,b<<i);
            }
            return res;
        }

下面贴张图，应该就很好理解了。满足为1，不满足上0  
![这里写图片描述][70]

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

## POW的实现 ##

> 在这里不使用的循环的原因是，那样太需要计算很多次，这里的temp用于保存上次的记录的结果，直接拿出来用，避免的了重复的计算，我们一次分为奇偶来讨论，如 x^4 可以拆分为`x^2*x^2 => x^(y/2)`，而奇数的话，我们可以用上次保存的偶数乘以x得到。`代码如下`：

public int pow(int x,int y) {
            if(y == 1) return x;
            int result = 0;
            int temp = pow(x,y/2);
            //y&1 可以验证奇偶 当y的二进制末尾不存在1即为偶数
            if((y&1) != 0) {
       //奇数
                result = x*temp*temp;
            }else {
       //偶数
                result = temp*temp;
            }
            return result;
        }

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

## 总结 ##

`全部代码清单`

public class Arithmetic { 
        public static void main(String[] args) {
            Arithmetic atri = new Arithmetic();
            System.out.println(atri.add(1, 2));
            System.out.println(atri.multiply(2, 3));
            System.out.println(atri.div(6, 3));
    
        }
    
        /** * a+b => 1111 + 1011 不带进位的相加 加上进位 * @param a * @param b * @return */
        public  int add(int a,int b) {
            if(b==0) {
                return a;
            }
    
            if(a == 0) {
                return b;
            }
            int sum=0,carry;//carry代表进位
            while(b!=0) {
                sum = a^b; //不带进位的相加
                carry = (a&b)<<1; //进位
                a = sum;
                b = carry;
            }
            return sum;
        }
        //取数值的相反数 用补码+1 得到相反数
        public int negative(int a) {
            return add(~a,1);
        }
    
        public int sub(int a,int b) {
            return add(negative(b),a);
        }
    
        public int multiply(int a,int b) {
            //利用map存放需要移动的位数，以及1向左移动i位的值
            Map<Integer,Integer> map = new HashMap<>();
            for(int i=0;i<32;i++) {
                map.put(1<<i, i);
            }
            int sum = 0;
            while(b>0) {
                int last = b&(~(b-1));//取得最后一个1;
                int count = map.get(last);//取得移动的位数
                sum = add(sum,a<<count);
                b = b&(b-1); //去掉最后一个1;
            }
            return sum;
        }
    
        public int div(int a,int b) {
            if(a<b) {
                return 0;
            }
            int bleft = 0;
            while((b<<bleft)<a) {
                bleft++;
            }
            int res = 0;
            for(int i=bleft;i>=0;i--) {
                if((b<<i)>a) continue;
                res |= (1<<i);
                a = sub(a,b<<i);
            }
            return res;
        }
    }

[70]: /images/20220523/9a9a60deee3e40978d536cf20a3067ed.png