用位运算实现整数加减乘除

首先回顾一下位运算

与(&) 两者均为1才为1,也就是遇0则0。(1001 & 1110 = 1000)

或(|) 两者均为0才是0,也就是遇1则1。(1001 | 1110 = 1111 )

异或(^)相同为0,不同为1。(1001 ^ 1110 = 0111)

左移(<<)A<<B,将A的值向左移动B的位数。左移一位相当于A乘2,左移B位相当于A乘2^B(101110<<3 ==110000 )

右移(>>和>>>)>>代表带符号右移,最高位补符号位 >>>代表不带符号右移,最高位补0。右移一位相当于除2,右移B位相当于除以2^B

(01110(14)>>2=00011(3))

(1111 0010(-14)>>2=1111 1100(-4))


加法

异或运算也叫无进位相加

1001 0110

^ 1110 0111

= 0111 0001

可以看出来0+1=1 1+1进位得0,但下一位运算忽略进位得1+1依然是0

进位信息可由与运算得出

/\1001 0110

& 1110 0111

= 1000 0110

进位信息是与运算的下一位也就是左移一位

/*
A+B = A ^ B + A & B << 1
    =(A^B) ^ (A & B << 1) + (A ^ B) & (A & B << 1) << 1
    =……
*/

这个过程可以一直进行下去,直到进位信息为0,结果就出来了。

例:46+20 = 66

/\0101110+0010100

=0111010+0001000

=0110010+0010000

=0100010+0100000

=0000010+1000000

=1000010+0000000(第一个不是符号位)

=66

用代码可以这样实现

public static int add(int a, int b) {
   int sum = a;//假如b一开始为0,答案就是a
      while (b != 0) {//进位信息为0结束
          sum = a ^ b;//无进位相加
          b = (a & b) << 1;//进位信息
          a = sum;
      }
   return sum;
}

减法

减法可作为加法的逆运算

A-B = A + (-B)

先写一个转换相反数的方法,即取反加一

public static int negNum(int n) {
    return add(~n, 1);
}

再调用加法即可

public static int minus(int a, int b) {
    return add(a, negNum(b));
}

乘法

/*
1010 * 101 = 1010 * 2^0 + 1010 * 2^2 
           = 1010 + 00000 + 101000
*/

这个好理解,101转换过来就是2^2+2^0,用乘法分配律就能转化,然后,根据左移的意义(左移B位相当于A乘2^B)也就很好理解。

public static int multi(int a, int b) {
    int res = 0;//初始为0
    while (b != 0) {//直到b彻底走完
        if ((b & 1) != 0) {//判断是否为1
            res = add(res, a);//为1就加进去
        }
        a <<= 1;//将a进行左移
        b >>>= 1;//b进行减少
    }
    return res;
}

除法

emmm
a/b=c
假设c为1001
a = b*2^0+b*2^3
c为0为上有1,3位位上有1
其余为0
所以计算c只需要知道c那些位置上需要1
假设a为1110,b为0101,找到c为1的位置,只需要去让b左移去够到a,但不超过a就可以,对应的c的位数上就应该为1,
b左移一位不超过a,左移两位大于a,所以c的第一位就是1,第0位是0
现在就需要将a减去刚刚左移出1位的b,也就是a - (b << 1) = 1110 - 1010 = 0100
接着发现0100与0101,0101已经大于0100,所以答案就是0010
看代码会发现并没有左移b,而是右移a,这是因为,假如一直左移b,会出现最高位也就是符号位变号,影响判断。
------
   public static int div(int a, int b) {
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;//全弄成正数
        int res = 0;
        for (int i = 30; i >= 0; i = minus(i, 1)) {//x为非负,没必要右移31位
            if ((x >> i) >= y) {//不移动y是因为怕符号位影响判断
                res |= (1 << i);//移动i位上设置为1
                x = minus(x, y << i);
            }
        }
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;//符号不相同就为负
    }

leetcode题目-两数相除

这道题同样可以用上述方法解决

再添加一个方法,其中最为关键是int的系统最小(Integer.MIN_VALUE)是在int范围没有相反数,这就需要分类讨论,

1.两个都是最小,相除得1

2.除数是最小,无论被除数为多少,结果都为0.(int)

3.被除数为最小,当除以-1时,题目要求返回系统最大,

其余数字可以这样计算先最小值加一,先计算一次结果,再与差再进行一次除法,举个例子

假设-20~19是一个范围,-20就是最小

计算-20/10。因为在(-20,19)内没有20,所以先计算

(-20+1)/ 10 = -1

-1*10 = -10

-20-(-10) = -10

-10 / 10 = -1

-1+(-1) = -2即为答案

 public static int divide(int a, int b) {
    if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
        return 1;
    } else if (b == Integer.MIN_VALUE) {
        return 0;
    } else if (a == Integer.MIN_VALUE) {
        if (b == negNum(1)) {
            return Integer.MAX_VALUE;
        } else {
            int c = div(add(a, 1), b);
            return add(c, div(minus(a, multi(c, b)), b));
        }
    } else {
        return div(a, b);
    }
 }
文章主体思路来自左程云老师的算法新手班第五节

评论

  1. 锐喙决吻
    Windows Chrome
    9月前
    2023-1-01 17:35:45

    good

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
-->