LeetCode的Easy题(一)

Description

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example

Given a = 1 and b = 2, return 3.

Thinking

一开始还以为是一个a+b question来作为测试的,仔细一看之后发现还有一些些意思的。很显然是要用位运算的组合来得到答案,不过具体要有哪些操作,只能让我们试一试才知道。

比如说:10001 与 101

  1. 10001 ^ 101 = 10100 xor运算之后发现,得到的式子恰好是两个数在不考虑进位情况下的加法运算(同时也是在不考虑借位情况下的减法运算);
  2. 10001 & 101 = 00001 and运算会让两个1变成1,当然这是我们加法中进位的标志,也是进的那个1,所以只需要左移一位就可以得到需要进位的值;
  3. 再用相同的方法递归的将上面两个加起来,直到进位是0就可以了。

Code

1
2
3
4
5
6
7
8
private int getSum(int a, int b) {
if(b == 0){
return a;
}
int sum = a ^ b;
int carry = (a & b) << 1;
return getSum(sum, carry);
}

Addition

显然我们可以借此类比出减法的算法:

1
2
3
4
5
6
7
8
private int getSub(int a, int b){
if(b == 0){
return a;
}
int sub = a ^ b;
int carry = ((~ a) & b) << 1;
return getSub(sub, carry);
}

只需要注意减法要退位的标志是被减数时0,减数是1,通过not、and运算可以得到结果。

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2018 Alex's Blog All Rights Reserved.

Yifeng Tang hält Urheberrechtsansprüche.