Java simple easy understand solution with explanation

• I have been confused about bit manipulation for a very long time. So I decide to do a summary about it here.

"&" 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:

https://en.wikipedia.org/wiki/Two%27s_complement

https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html

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;
}
``````

• ^ is xor, not or

• If a b are all negative, how should we deal with the sign bit?

• cool thought, actually it can handle negative number.

for example, a = -1 (1111), b = 2 (0010),

i = 0, carry = 0010, a = 1101, b = 0100

i = 1, carry = 0100, a = 1001, b = 1000

i = 2, carry = 1000, a = 0001, b = 0000, stop, return a(1)

• thanks, updated.:)

• 2 (0010) & 7 (0111) = 2 (0010) not 9

• thanks for the correction. :)

• Hi, could you explain a little bit more about your public int getSubtract(int a, int b) {} function? I understand how the addition works, but not how the subtraction works.

• In the getSubtract method, why int borrow = (~a) & b instead of int borrow = ((~a)+1) & b;

• Building on top of addition, we can also do multiplication without + - * /:

``````    public int getProduct(int a, int b) {
if (a==0 || b==0) return 0;
int result = 0;
while (b != 0) {
if ((b & 1) != 0) {
result = getSum(a,result);
}
a <<= 1;
b >>>= 1;
}
return result;
}
``````

• @Wayne3223
It depends whether 'a' is the minuend or subtrahend.
i.e. difference = minuend - subtrahend.

If you write it as "subtract 3 from 2", and see 'a' as 3, and 'b' as 2. then the formula should be
borrow = ((~a)+1) & b;

See an example here. When b becomes 0, a = -1.
a = 3
b = 2

a = 0011
b = 0010

borrow = 1101 & 0010 = 0001
a = 0001
b = 0010

borrow = 1111 & 0010 = 0010
a = 0011
b = 0100

borrow = 1101 & 0100 = 0100
a = 0111
b = 1000

borrow = 1001 & 1000 = 1000
a = 1111
b = 0000

so a = -1;

However, if you write it as just "3 - 2", and take 'a' as 3 and 'b' as 2, then formula for borrow is
borrow = (~a) & b;

See an example below.
subtract 2 from 3.
a = 3
b = 2

a = 0011
b = 0010

borrow = 1100 & 0010 = 0000
a = 0001
b = 0000

a = 1;

So I believe it depends on the position of a.
If it is a - b then borrow = (~a) & b;
else if it is b - a then borrow = ((~a)+1) & b; or (~b) & a;
Honestly, I prefer the former one.
Correct me if anything is wrong here.

• @zhaolz
A better subtraction code, for if 'a' = 0, or 'b' = 0;
I'm considering 'a' as 'minuend' and 'b' as 'subtrahend'.
i.e. 'a-b'
e.g. '2 - 3', this code will return answer as '-1'. Let me know if there is any mistake.

``````public static int getSubtract(int a, int b) {
if(a == 0) return (~b + 1);
if(b == 0) return a;

int borrow = 0;
while(b != 0) {
borrow = (~a) & b;
a = a ^ b;
b = borrow << 1;
}
return a;
}
``````

• @ztztzt8888
Hey this is great. I have upvoted your code, but would you please explain the logic behind this. I didn't understand it. Thanks. Really appreciate it.
I did try to trace it using a two digit multiplication, but didn't understand how it's working.

10 * 25.
a = 10, b = 25.

a = 0000 1010
b = 0001 1001
b & 1 => 0000 0001
result = 10;
a = 0001 0100
b = 0000 1100

b & 1 => 0000 0000
a = 0010 1000
b = 0000 0110

b & 1 => 0000 0000
a = 0101 0000
b = 0000 0011

b & 1 => 0000 0001
result = 10 + 80 = 90
a = 1010 0000
b = 0000 0001

b & 1 => 0000 0001
result = 90 + 128 + 32 = 250
a = 0100 0000
b = 0000 0000

return result = 250;

• @SanD
In your case 1, it is b-a=b+(-a) actually. So I prefer "carry= ((~a)+1) & b", not "borrow = ((~a)+1) & b"

• @xiangmo I hope you understand that when we do addition, we use the term "carry", and "borrow" when we do subtraction. Clearly, what you are talking about is subtraction, so I think it should be "borrow". Nevertheless, it is up to you what you want to name the variable as. I just gave what is usually used (terminology).

• Compact Code! Any idea on how to prove the algorithm will finally end (that is, while loop is not infinite)?

• borrow = 1101 & 0010 = 0001

1101 & 0010 = 0000?

• @StellaWu Hey, yeah that is a mistake. I'll recorrect it.

• @shaokunzou I have figured out the correctness of this algorithm when two integers are both nonnegative.
As implied in the explanation, if carry = 0, a ^ b would be the sum, otherwise (carry << 1) + (a ^ b) would be the sum.
Since mathematically addition would not be infinite, the while loop is not infinite.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.