Sum of Two Integers


  • 0
    F

    Calculate the sum of two integers, but you are not allowed to use the operator + and -.

    Example:

    Given [1, 2], return 3.
    

  • 1
    G

    One trivial solution is that, each time we read in one bit for each integer and use the following true table in wiki link, then keep accumulating:

    https://en.wikipedia.org/wiki/Adder_(electronics)
    

  • 0
    F

    @GoGoDong Yes, we can add two integers each time a bit, but we can also consider that what do we do when adding two decimal integers using the operator +, for example 14 + 16, we can separate the sum into 2 parts(steps), 20 + 10, 20 corresponding to 1 + 1 (= 2) and 4 + 6 (= 0), 10 corresponding to 4 + 6 (=10)...so 14 + 16 becomes a new problem 20 + 10...


  • 2
    4

    @fujiaozhu
    I don't see how your explanation avoids using the + operator.

    Also I do not consider this an "easy" problem as (unless you know Adders by heart) have to come up with an adder on your own.

    Furthermore, if you do it via bit manipulation the bit representation of the numbers needs to be considered especially when handling negative numbers.


  • 0
    F

  • 1
    4

    @fujiaozhu
    This is how I solved it, yeah.

    I am on about your explanation in decimal that clearly uses the + operator.

    Furthermore, I am stating that the problem is not "easy" because you need to be familiar with how an adder works PLUS you need to take into account the underlying implementation/representation of integers in the language chosen (e.g. python).


  • 0
    4

    As a general hint to novices who want to step up their python game:

    You can make use of import ctypes to get a c-style twos complement representation in Python.
    The tests run for 32bit signed integegers.

    https://docs.python.org/2/library/ctypes.html?highlight=ctypes.c_int#ctypes.c_int32


  • 0
    M

    @fujiaozhu

    I'm not sure if it's allowed, but this solution doesn't use + or -

    Idea:

    • create new empty list L

    • for each number in the given list, construct a range from 0 to this number (via 'range') and loop on this range, appending 1 to list L.

    • at the end, simply return the length of L.

    def adder(li):
      lii = []
      for i in li:
        for j in range(0,i):
          lii.append(1)
      return len(lii)
    

    adder( [1,2] )
    // 4 because len( [1, 1, 1] ) = 3


  • 0
    F

    @mingik Hi, what if a and b are quite large? This solution seems not that efficient.


  • 0
    M

    @fujiaozhu

    I see -- if large numbers are involved, then perhaps it'll be more efficient to use bytearrays instead:

    def adder(li):
      ba = bytearray()
      for i in li:
        ba.extend( bytearray(i) )
      return len(ba)
    

    But it will still fail to add some quite large numbers...


  • 0
    H

    @fujiaozhu hi, When the integers go large. the expected answer seems to be wrong.
    e.g. a=1549872, b=2864423554532. The answer comes out -318082028


Log in to reply
 

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