位运算

位运算在程序设计中非常重要,特别是有复杂运算的时候,位计算的高效率优势发挥地淋漓尽致。BigDecimal底层加减乘除运算都是运用了位运算,如果在大学区间有学到位运算符,应该重视起来,不要像作者君这样,现在要去捡起来。

以下内容都是假定各位都知道位运算的情况下。


加法

先看一道题

给出两个整数 aa 和 bb , 求他们的和, 但不能使用 ++ 等数学运算符。
说明
a和b都是 32位 整数么?
是的
我可以使用位运算符么?
当然可以
样例
如果 a=1 并且 b=2,返回3。
(来自lintcode)

这个题目只能用位运算符来做。
首先我们看看十进制中有比较好的算法。
为了缩短篇幅,我这里省略了一些思考过程,但是不影响读者的理解,直接举一个复杂点的例子:
例子
12345+67890
最终的结果是sum,进位为carry
从低位加起

step 1  sum = 5 + 0 = 5;                                    carry = 0;
step 2  sum = sum + ((carry + 4 + 9) % 10)*10 = 35;         carry = (carry + 4 + 9)/10 = 1;
step 3  sum = sum + ((carry + 3 + 8) % 10)*100 = 235;       carry = (carry + 3 + 8)/10 = 1;
step 4  sum = sum + ((caary + 2 + 7) % 10)*1000 = 235;      carry = (carry + 2 + 9)/10 = 1;
step 5  sum = sum + ((caary + 1 + 6) % 10)*10000 = 80235;   carry = (carry + 2 + 9)/10 = 0;

上面说了十进制的算法,但是它在二进制中是否可以借鉴呢?答案是肯定的。
上面的算法其实就是对sum和carry的运算。

首先这道题目是要求只能用位运算符,二进制是没有很多位运算符的,只有下面这些:
这里写图片描述
那么这道题的算法该怎么设计呢?
我们先看看异或这个东西。

case 1: 1 ^ 6 (十进制) = (0000 0001) ^ (0000 0110) = 0000 0110 = 7
case 2 : 1 ^ 7 (十进制) = (0000 0001) ^ (0000 0111) = 0000 0110 = 6
(其实根据这个很容易知道异或可以做参数互换,这里不展开讲。)

首先1 ^ 6 = 7 , 结果和1 + 6 = 7很像。那么我们能往这个方向思考嘛?答案是可以的。但是要解决以下case 2的问题。
借鉴一下上面十进制的推导过程,那么我们假设两个二进制做异或的值为sum,进位carry需要巧妙设计一下:首先两个数相加和是2则进位,是二进制的进位制,那么我们可以换成这样 (a & b) << 1。记相加的两个数做与之后向左移意味。

我们试着这样推导一下:

                    0000 0001     1
                  ^ 0000 0111     7
step 1: sum   =     0000 0110     6
        carry =   ^ 0000 0010     2
step 2: sum   =     0000 0100     4
        carry =   ^ 0000 0100     4
step 3: sum   =     0000 0000     0
        carry =   ^ 0000 1000     8
step 4: sum   =     0000 1000     8
        carry =     0000 0000     0                

观察一下可以得出结论,step2,3,4都是重复step1的操作。
后面可以继续推论其它的例子。其实这个用例是前人经过很多努力推导出来的,我这里只是方便大家理解才重新推导一下而已。
根据上面的代码很容易写出这道题的解决方法:

    public static int add(int num1, int num2) {
        int sum = num1 ^ num2;
        int carry = (num1 & num2) << 1;
        while (carry != 0) {
            int a = sum;
            int b = carry;
            sum = a ^ b;
            carry = (a & b) << 1;
        }
        return sum;
    }

减法

减法就比较简单了。打个比方a-b。
在十进制中我们很容易得出a-b = a + (-b)。
同样的这个在二进制中同样合适,那么剩下的问题是-b在二进制中怎么表示。
-b在二进制中是使用补码加1的方式表示的,这个在计算机原理课程已经讲了,我这里直接使用这个结论,那么很容易得到以下内容

    public static int substract(int num1, int num2) {
        int substactor = add(~num2, 1);
        return add(num1, substactor);
    }

乘法

我们先来看看一道题目:
… 待续

版权声明:本文为ydonghao2原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ydonghao2/article/details/80584117