Cracking The Coding Interview/Q 18.1

From Software Engineers Wiki
Jump to: navigation, search

Write a function that adds two numbers. You should not use + or any arithmetic operators.

Answer

When we add two numbers,

  • bit 0 + bit 0 = bit 0
  • bit 1 + bit 0 = bit 1
  • bit 0 + bit 1 = bit 1
  • bit 1 + bit 1 = bit 0, carry 1 to next bit

So adding two number a, b is same as (a ^ b) + carry, in which carry is (a & b) << 1

def bitwiseAdd(a, b):
        add_without_carry = a ^ b
        carry = a & b
        return add_without_carry if (carry == 0) else bitwiseAdd(add_without_carry, carry << 1)

Or in simple form without using recursion.

def bitwiseAdd(a, b):
        while (b != 0):
                a, b = a ^ b, (a & b) << 1
        return a

Test program

def addTest(a, b):
        result1 = a + b
        result2 = bitwiseAdd(a, b)
        print("{0} + {1} = {2} : {3}".format(a, b, result1, "Correct" if (result1 == result2) else "Incorrect"))

def main():
        addTest(12345, 67890)
        addTest(0x33333333, 0x13131313)
        addTest(0x88888888, 0x11111111)

main()

Reference

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox