https://leetcode.com/problems/sum-of-two-integers/
http://www.cnblogs.com/grandyang/p/5631814.html
X. https://leetcode.com/problems/sum-of-two-integers/discuss/84282/Python-solution-with-no-%22%2B-*%22-completely-bit-manipulation-guaranteed
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.
Given a = 1 and b = 2, return 3.
解法I 位运算（Bit Manipulation）异或 + 移位
http://www.geeksforgeeks.org/add-two-numbers-without-using-arithmetic-operators/
Sum of two bits can be obtained by performing XOR (^) of the two bits. Carry bit can be obtained by performing AND (&) of two bits.
Above is simple Half Adder logic that can be used to add 2 single bits. We can extend this logic for integers. If x and y don’t have set bits at same position(s), then bitwise XOR (^) of x and y gives the sum of x and y. To incorporate common set bits also, bitwise AND (&) is used. Bitwise AND of x and y gives all carry bits. We calculate (x & y) << 1 and add it to x ^ y to get the required result.
Above is simple Half Adder logic that can be used to add 2 single bits. We can extend this logic for integers. If x and y don’t have set bits at same position(s), then bitwise XOR (^) of x and y gives the sum of x and y. To incorporate common set bits also, bitwise AND (&) is used. Bitwise AND of x and y gives all carry bits. We calculate (x & y) << 1 and add it to x ^ y to get the required result.
int Add(int x, int y){ // Iterate till there is no carry while (y != 0) { // carry now contains common set bits of x and y int carry = x & y; // Sum of bits of x and y where at least one of the bits is not set x = x ^ y; // Carry is shifted by one so that adding it to x gives the required sum y = carry << 1; } return x;}
public int getSum(int a, int b) {
while (b != 0) {
int c = a ^ b;
b = (a & b) << 1;
a = c;
}
return a;
}
解法II 位运算（Bit Manipulation) 模拟加法
public int getSum(int a, int b) {
int r = 0, c = 0, p = 1;
while ((a | b | c) != 0) {
if (((a ^ b ^ c) & 1) != 0)
r |= p;
p <<= 1;
c = (a & b | b & c | a & c) & 1;
a >>>= 1;
b >>>= 1;
}
return r;
}
int getSum(int a, int b) { if (b == 0) return a; int sum = a ^ b; int carry = (a & b) << 1; return getSum(sum, carry); }
int getSum(int a, int b) { return b == 0 ? a : getSum(a ^ b, (a & b) << 1); }
public int getSum(int a, int b) {
if(a == 0){
return b;
}
if(b == 0){
return a;
}
int sum = a ^ b;
int carry = (a & b) <<1;
return getSum(sum, carry);
}
首先要知道，异或也被称为“模2和” ，so 这题就是运用异或的位运算啦。
我们可以每次取最低位来计算, 然后每次右移一位，注意点有：
- 进位为两个数字1
- 负数的情况下，右移最高位补的是1 ,因此值得注意要取到什么时候为止。 java有一个无符号右移>>>高位补0，因此结束条件可以为a!=0 || b!=0
public int getSum(int a, int b) {
int ans = 0, carry = 0;
for (int i = 0; a!=0 || b!=0; a >>>= 1, b >>>= 1, i++) {
int lower_a = a & 1, lower_b = b & 1;
ans |= (lower_a ^ lower_b ^ carry) << i;
carry = (carry & lower_a) | (carry & lower_b) | (lower_a & lower_b);
}
return ans;
}
X. https://leetcode.com/problems/sum-of-two-integers/discuss/84282/Python-solution-with-no-%22%2B-*%22-completely-bit-manipulation-guaranteed
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
# 32 bits integer max
MAX = 0x7FFFFFFF
# 32 bits interger min
MIN = 0x80000000
# mask to get last 32 bits
mask = 0xFFFFFFFF
while b != 0:
# ^ get different bits and & gets double 1s, << moves carry
a, b = (a ^ b) & mask, ((a & b) << 1) & mask
# if a is negative, get a's 32 bits complement positive first
# then get 32-bit positive's Python complement negative
return a if a <= MAX else ~(a ^ mask)
"&" AND operation, for example, 2 (0010) & 7 (0111) => 2 (0010)
"^" XOR operation, for example, 2 (0010) ^ 7 (0111) => 5 (0101)
"~" NOT operation, for example, ~2(0010) => -3 (1101) what??? Don't get frustrated here. It's called two's complement.
1111 is -1, in two's complement
1110 is -2, which is ~2 + 1, ~0010 => 1101, 1101 + 1 = 1110 => 2
1101 is -3, which is ~3 + 1
so if you want to get a negative number, you can simply do ~x + 1
Reference:
For this, problem, for example, we have a = 1, b = 3,
In bit representation, a = 0001, b = 0011,
First, we can use "and"("&") operation between a and b to find a carry.
carry = a & b, then carry = 0001
Second, we can use "xor" ("^") operation between a and b to find the different bit, and assign it to a,
Then, we shift carry one position left and assign it to b, b = 0010.
Iterate until there is no carry (or b == 0)
// Iterative
public int getSum(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
while (b != 0) {
int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
// Iterative
public int getSubtract(int a, int b) {
while (b != 0) {
int borrow = (~a) & b;
a = a ^ b;
b = borrow << 1;
}
return a;
}
// Recursive
public int getSum(int a, int b) {
return (b == 0) ? a : getSum(a ^ b, (a & b) << 1);
}
// Recursive
public int getSubtract(int a, int b) {
return (b == 0) ? a : getSubtract(a ^ b, (~a & b) << 1);
}
// Get negative number
public int negate(int x) {
return ~x + 1;
}