Add numbers in hexadecimal base without converting bases?

Question

I need to write a function which gets two numbers in hexadecimal base, and calculates the sum of both of them, I'm not allowed to convert them to decimal base, the code is supposed to calculate it "manually" using loops. for example this is how it should work:

 1
 1 f 5  (A) 
+  5 a  (B) 
------------- 
= 2 4 f 

Here is an input example: >>> add("a5", "17") 'bc'

I've started building my code but I got stuck, I thought I would divide into three ifs, one that would sum up only numbers, other sums numbers and letters, and the third one sums letters, but I don't know how to continue from here:

def add_hex(A,B):
lstA = [int(l) for l in str(A)]
lstB = [int(l) for l in str(B)]

if len(A)>len(B):
    A=B
    B=A
A='0'*(len(B)-len(A))+A
remainder=False
result=''
for i in range(len(B)-1)
if (A[i]>0 and A[i]<10) and (B[i]>0 and B[i]<10):
   A[i]+B[i]=result
   if A[i]+B[i]>10:
       result+='1'

Any help is greatly appreciated, I have no clue how to start on this!

Answer 1

I think we just remember the pattern of addition. Like following.

"0" + "0" = "0"
"0" + "1" = "1"
"0" + "2" = "2"
       .
       .
       .
"f" + "d" = "1b"
"f" + "e" = "1c"
"f" + "f" = "1e"

We have dictionary of all of the pattern because we've learned it in school or somewhere. And we've also learned carry.

So I think this seems like manual addition algorithm.

1. Remembering the pattern include carry.
2. Calculating
   • Translate two digit to one digit(a+b->c).
   • Treat carry correctly.

And here is my code for that. But it may be a bit tricky.

import itertools

def add_hex(A,B):
    A = "0"+A
    B = "0"+B
    #Remember all pattern include carry in variable d.
    i2h = dict(zip(range(16), "0123456789abcdef"))
    a = [(i,j) for i in "0123456789abcdef" for j in "0123456789abcdef"]
    b = list(map(lambda t: int(t[0],16)+int(t[1],16), a))
    c = ["0"+i2h[i] if i<16 else "1"+i2h[i-16] for i in b]#list of digit include carry
    d = dict(zip(a,c))#d={(digit,digit):digit,,,}
    #Calculate with variable d.
    result = ""
    cur = "0"
    nex = "0"
    for i in itertools.izip_longest(A[::-1], B[::-1], fillvalue = "0"):
        cur = d[(nex, d[i][1])][1]                   #cur = carry + digit + digit
        if d[i][0]=='1' or d[(nex, d[i][1])][0]=='1':#nex = carry = carry + digit + digit
            nex = "1"
        else:
            nex = "0"
        result += cur

    return result[::-1]

#Test
A = "fedcba"
B = "012346"
print add_hex(A,B)    
print hex(int(A,16)+int(B,16))#For validation

I hope it helps. :)

Answer 2

You can have a sub-function that adds two single-digit hex numbers and returns their single-digit sum and a carry (either 0 or 1). This function will take three inputs: two numbers you want to add and a carry-in. You can then loop through the digits of the two numbers you want to add from least significant to most significant, and apply this function for every pair of digits while taking into account the carry at each stage.

So let's try your example:

A 5
1 7 +

We start at the least significant digits, 5 and 7, and perform the 1-digit addition. 5₁₆ + 7₁₆ = 12₁₀. 12₁₀ is less than 16₁₀, so the output of our 1-digit add is 12₁₀ = C₁₆ with a carry of 0.

Now we add A and 1 (our carry-in is 0 so we can just add them normally). A₁₆ + 1₁₆ = 11₁₀. 11₁₀ is less than 16₁₀, so the output of our 1-digit add is 11₁₀ = B₁₆ with a carry of 0. (If we had a non-zero carry-in, we would just add 1 to this value.)

Hence, our overall result is:

A 5
1 7 +
-----
B C