Binary addition carry and overflow in Python

Question

I am trying to build a function that calculates the checksum of four elements in an 8-bit array. What I am struggling with is the carry and overflow of binary addition. For example:

it overflows we wraparound the most left with the most right so it becomes 011.

I am able to do the calculation using bin. I can do the above if the right most value is 0 and the left most value is 1 because in that case we won't have to carry anything to the next value from the right.

What I am struggling with is, something like this scenario:

it overflows again but this time we have to wraparound 1(left most)+1(right most) = 10 which means we will take 0 and carry 1 to the next right most (0) in this case. The final result in that case would be = 110

if it was 1 instead of 0 we will get 10 again and we will have to carry 1 to the next value and so on and so forth.

See my code below:

def overFlow(sumN):  
  # this works if my left most is 1 and my right most is 0
  if(sumN[8] == "0"):
    print("--------------------")
    overflow = bin(int(sumN[0],2) + int(sumN[8],2))[2:]
    temp = list(sumN)
    temp.pop(0)
    temp.pop(7)
    temp.append(overflow)
    newtemp= ""
    for i in temp:
      newtemp += i  
    sumN = newtemp
    print(sumN)
    print("--------------------")
  # else:
  # this is where I am stuck

  return sumN

def checksum(message):
  var1 = message[0][2:]
  var2 = message[1][2:]
  var3 = message[2][2:]
  var4 = message[3][2:]
  bit_len = 8
  print(len(var1))

  sum1 = bin(int(var1,2) + int(var2,2))[2:]
  if(len(sum1) > bit_len):
    sum1 = overFlow(sum1)
  print("var 1  " +var1+"\nvar 2  "+var2+"\nSum    "+sum1)
  sum2 = bin(int(sum1,2) + int(var3,2))[2:]
  if(len(sum2) > bit_len):
    sum2 = overFlow(sum2)
  print("var 1  " +sum1+"\nvar 2  "+var3+"\nSum    "+sum2)
  sum3 = bin(int(sum2,2) + int(var4,2))[2:]
  if(len(sum3) > bit_len):
    sum3 = overFlow(sum3)
  print("var 1  " +sum2+"\nvar 2  "+var4+"\nSum    "+sum3)
  comp = ""
  tot_sum = sum3
  n = len(tot_sum)
  for i in range(n):
    if (tot_sum[i]== '0'):
      comp+= '1';
    if (tot_sum[i]== '1'):
      comp+= '0';
  
  print(f"1's complement is = {comp}")

message = ['0b10110110','0b11011100','0b01100111','0b01111101']
checksum(message);

Any help is much appreciated.

UPDATE: The right output for the message above should be as follow:

var1  10110110
var2  11011100
sum1 110010010 "overflow so we take left most and add it with right most" 1+0 = 1
sum1 becomes = 10010011

sum1  10010011
var3  01100111
sum3  11111010 "no overflow, so we do nothing"

sum3  11111010
var4  01111101
     101110111 "overflow left most(1) + right most (1) = 10" we take zero and carry one to the next right most number
        which is 1 which will give me again 10 so we take zero and carry one until we don't have to carry anymore
the final result should be **01110000** 
after 1's compelement it should be **10001111**

and this is my current output:

var 1  10110110
var 2  11011100
Sum    10010011
var 1  10010011
var 2  01100111
Sum    11111010
var 1  11111010
var 2  01111101
Sum    101110111
1's complement or the checksum is = 010001000

Please provide the expected MRE. Show where the intermediate results deviate from the ones you expect. We should be able to paste a single block of your code into file, run it, and reproduce your problem. This also lets us test any suggestions in your context. — Prune
– Prune, Commented Nov 25, 2020 at 2:10
You have the code already. Trace the execution (generally done with strategically-placed print statements). Where does your wrap-around code differ from what you expect? — Prune
– Prune, Commented Nov 25, 2020 at 2:11
just cut the number with the overflow into 2 numbers, 1 is 1 char (overflow) and other is 8 chars, and treat these the same as you do for the 2 8-character binary numbers. Repeat this wraparound till you don't have an overflow — rioV8
– rioV8, Commented Nov 25, 2020 at 2:48
remove the semicolons, for ones-complement use string.translate — rioV8
– rioV8, Commented Nov 25, 2020 at 2:50
in 18 lines of code the result is 1's complement is = 0000111 — rioV8
– rioV8, Commented Nov 25, 2020 at 3:18

RufusVS · Accepted Answer · 2020-11-25 04:12:20Z

1

This is a simple 8-bit checksum routine, with rollover. There is a wrapper function that accepts and returns data in the original ascii binary format. But you really just want to work with bin array and the first function.

def checksum(bin_array):
    result = 0
    for num in bin_array:
        result += num
        if result >= 256:
            result -=255 # subtract 256 and add one
        # print(bin(result)) # show partial result if desired
    return result

def checksum_binstrs(ascii_bin_array):
    bin_array = list(map(lambda x: int(x,2),ascii_bin_array)) # convert to binary array
    result = checksum(bin_array)
    return bin(result) # convert to binary string


message = ['0b10110110','0b11011100','0b01100111','0b01111101']

print (checksum_binstrs(message))

answered Nov 25, 2020 at 4:12

RufusVS

4,1553 gold badges33 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ozeus Over a year ago

ah I feel so terrible looking at my code. I see how you approached this, I didn't think of it that way. Thank you for your time.

Collectives™ on Stack Overflow

Binary addition carry and overflow in Python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related