Writing the two's complement of a positive 16 bit binary number in Python

Question

I must only use loops, not any special built-in python library functions. Say the input is 0000000000000110, my desired output is 1111111111111001.

I know two methods of doing this but I'm having troubling programming at least one of them to work in python.

The first method: Loop through all the digits, if it's a 0 then change it to a 1, if it's a 1 then change it to a 0. This is the one's complement. This is not an issue. Then add 1 base 2 to the rightmost binary bit and the two's complement is generated. The PROBLEM I have with this method is carrying 1 when adding throughout the bits if a 1 needs to be carried.

The second method (Probably easier): Loop through the binary number starting from the rightmost bit. Until the first 1 is read don't invert the number. Once 1 is read, don't invert the first 1. But invert all the bits to the left of the first 1 that's read (remember I'm looping through the number starting from the rightmost bit).

Simple 8-bit example) 00000110 loop through the number starting from the rightmost bit 0 (no change from original) 1 (no change from original) 0 (inverted from original) 1 (inverted from original) 1 (inverted from original) 1 (inverted from original) 1 (inverted from original) 1 (inverted from original)

The complication I'm having with implementing method into a program in python is once 1 is read I have a counter that increases by one. So I say if i == 0 or i == 1: don't invert if i > 1 : invert

However, there's a small issue with this you can see from the example I've given below. For example) 1101 1 0 PROBLEM: (i is still equal to 1) 0 0

When I want to get: 1101 1 1 0 0

#second method
#input is a string
def twosComp(num) :
  pile = ""
  pile2 = ""
  pile3 = ""
  i = 0

  #reverses the order of the bits(i.e. first bit in num is the last bit in 
  #pile) 
  for bit in num :
    pile = bit + pile
  print pile

 #SUPPOSED TO DO THE TWO'S COMPLEMENT (BUT THE I COUNTER CAUSES A PROBLEM)
  for bit in pile :
   if bit == "1" :
     i += 1
   if i == 0 or i == 1 :
     if bit == "0" :
       pile2 = pile2 + "0"
     elif bit == "1" :
       pile2 = pile2 + "1"
   elif i > 1 :
     if bit == "0" :
       pile2 = pile2 + "1"
     elif bit == "1" :
       pile2 = pile2 + "0"

   #reverses the order of the bits back to the correct order
   for bit in pile2 :
     pile3 = bit + pile3
   print pile3
   #>>> twosComp("1101")
   #1011
   #0001
   #pile3 the last output should be 0011


#method 1
def twosCompMOne(num) :
   pile = ""
   pile2 = ""
   pile3 = ""

   #reverses the order of the bits 
   for bit in num :
     pile = bit + pile
   print pile

  #inverts all the bits in pile
  for bit in pile :
    if bit == "0" :
      pile2 = pile2 + "1"
    if bit == "1" :
      pile2 = pile2 + "0"

  #reverses the order of the bits back to the correct order
  for bit in pile2 :
    pile3 = bit + pile3
  print pile3
  #Now I don't know how to do the add 1 carrying by looping

Please post the code that you have attempted so far for both methods — Andreas
– Andreas, Commented Nov 27, 2018 at 2:25
No bit shifting or addition either I presume? Because looping over individual bits in Python is no trivial task. — iz_
– iz_, Commented Nov 27, 2018 at 2:27

ShadowRanger · Accepted Answer · 2018-11-30 14:43:07Z

1

You have the general idea right. In this solution, first we get the one's complement, then we add one to the result as you expect. The thing to note is that adding one to a binary number is relatively easy (even in string representation).

The key point is keeping track of the carry. As soon as you add "1" to a "0", you do not have to carry any more. Rather than use a fancy algorithm, we will stick to the basic steps.

def invert(bin_string):
    """string -> string
    return the string representation of inverting every bit of a binary number
    represented by `bin_string`
    """
    return "".join("0" if i == "1" else "1" for i in bin_string)

Now for the actual 2's complement

def twos_comp(bin_string):
    """string -> string
    return a string representing the 2's complement of `bin_string`
    """
    addendum = 1
    res = ""
    for i in invert(string)[::-1]:
        if not addendum:
            res = i + res
        elif i == "0":
            res = "1" + res
            addendum = 0
        else:
            res = "0" + res
    return res

With this definition:

>>> twos_comp("1101")
'0011'
>>> twos_comp("110110")
'001010'

As expected

edited Nov 30, 2018 at 14:43

ShadowRanger

158k12 gold badges221 silver badges315 bronze badges

answered Nov 27, 2018 at 3:16

Xero Smith

2,0861 gold badge17 silver badges21 bronze badges

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

2 Comments

user8408080 Over a year ago

You should rather not use is for this kind of testing as it compares ids of the objects

Xero Smith Over a year ago

fair enough, especially if the string has not be interned. I'd update the comparison to ==

Collectives™ on Stack Overflow

Writing the two's complement of a positive 16 bit binary number in Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related