位运算实现加减乘除

加法

一位加法时,和是x XOR y的结果,而进位恰好是x AND y的结果.
多位加法时,可将x, y的每一位级联计算:先计算x和y的第零位,将计算所得的进位传入到x和y的第一位的计算中,依次进行直到计算完最高位为止,此时将每一位计算所得的和连接起来就是最终的和。计算机中的加法也是使用这种原理来实现的。
然而,逐位取出计算操作复杂,可以一次求出所有位上的和及进位,然后递归调用此方法直至进位为0。

1
2
3
4
5
6
7
8
9
10
11
public int add(int x, int y) {
// if(y==0)
// return x;
// return add(x ^ y,(x & y) << 1);
while (y != 0) {
int tmp = x ^ y;
y = (x & y) << 1;
x = tmp;
}
return x;
}

减法

减法是加法的逆运算,加法中的可以从低位开始依次往上传递进位,而且高位对低位的计算不产生影响。而减法则需要从高位获得借位,高位会对低位的计算产生影响。如果是小数字减大数字则计算过程更复杂,因此直接实现减法对计算机来说很复杂,而且效率很低。因此一般通过转化成相反数的加法完成,而只要想得到一个数的相反数,只要对这个数求2-补码就可以了,即取反加1操作。

1
2
3
public int subtract(int x, int y) {
return add(x, add(~y, 1));
}

乘法

根据乘法演算的过程,

  • 根据乘数每一位为1还是为0,决定相加数取被乘数移位后的值还是取0
  • 各相加数从乘数的最低位开始求值,并逐次将相加数(被乘数)左移一位,然后求和
  • 符号位根据同号为正异号为负的原则
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    /**
    1 0 1 1
    * 1 1 0 1
    ------------------
    1 1 0 1
    1 1 0 1 0
    0 0 0 0 0 0
    1 1 0 1 0 0 0
    ------------------
    1 0 0 0 1 1 1 1
    **/
    public int multiply(int x, int y) {
    int ans = 0;
    int sign = 0;
    if (x < 0) {
    sign = ~sign;
    x = add(~x, 1);
    }
    if (y < 0) {
    sign = ~sign;
    y = add(~y, 1);
    }
    while (y > 0) {
    if ((y & 1) > 0)
    ans += x;
    x <<= 1;
    y >>= 1;
    }
    if(sign>0)
    return add(~ans, 1);
    else
    return ans;
    }

除法

除法就是由乘法的过程逆推,依次减掉(如果x够减的)y^(2^31),y^(2^30),…y^8,y^4,y^2,y^1。减掉相应数量的y就在结果加上相应的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int divide(int x, int y) {
int ans = 0;
int sign = 0;
if (x < 0) {
sign = ~sign;
x = add(~x, 1);
}
if (y < 0) {
sign = ~sign;
y = add(~y, 1);
}
for (int i = 31; i >= 0; i--) {
if (x >= (y<<i)) {
x -= y<<i;
ans+= 1 << i;
}
}
if(sign>0)
return add(~ans, 1);
else
return ans;
return ans;
}