371. Sum of Two Integers

Problem:
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.

3/22/2017 update:
See example below: Use XOR, we can get the bits without carry, use & we can get carry before shift left by 1. 

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = a&b;
            a = a^b;
            b = carry << 1;
        }
        return a;
    }
}
Analysis:
Shift a&b to left by 1 bit makes carry of a+b. a^b means a+b without considering carry.
Solution:


 class Solution {  
   public int getSum(int a, int b) {  
    while (b!=0) {  
      int _a = a ^ b;  
      int _b = (a & b) << 1;  
      a = _a;  
      b = _b;  
    }    
   return a;  
   }  
 }  

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array