Sum of Two Integers

Posted on Updated on

Screen Shot 2016-08-25 at 8.00.23 PMProblem

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.

Solution

An excellent bitwise operation related problems summary

One more summary of bitwise operations

First keep in mind that “+/-” cannot be used anywhere.

The key ideas are bitwise operations and recursion:

  1. Bitwise operations:
    • “^” / xor is to remove the same bits and keep the distinct bits, actually like single bit adds of 0 + 1 = 1; here it’s like doing addition for different bits, so that only same bits 0 + 0/1 + 1 are left
    • since 0 + 0 has no effects on results, so only care about 1 + 1; this generates the carry. To get the correct bit location of carry, a left shift is needed, which means
      (a&b) << 1
  2. Recursion:
    • to generate the ^ plus carry, without using “+”. Use recursion to repeatedly add the above two bit operations
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s