Java simple easy understand solution with explanation


  • 227
    Z

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

  • 0
    R

    ^ is xor, not or


  • 2
    S

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


  • 3
    Z

    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)


  • 0
    Z

    thanks, updated.:)


  • 0
    R

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


  • 2
    Z

    thanks for the correction. :)


  • 3
    W

    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.


  • 9
    W

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


  • 8
    Z

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

  • 7
    S

    @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.


  • 3
    S

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

  • 2
    S

    @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;


  • 0

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


  • 1
    S

    @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).


  • 0
    L

  • 0

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


  • 1
    S

    @SanD said in Java simple easy understand solution with explanation:

    borrow = 1101 & 0010 = 0001

    1101 & 0010 = 0000?


  • 1
    S

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


  • 1

    @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.


Log in to reply
 

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