parameters: (a, b, bits_to_compute=None)
return_statement: return s
docstring: Add the bits a[k-1], ..., a[0] and b[k-1], ..., b[0], return k+1
          bits s[0], ... , s[k]
docstring_summary: Add the bits a[k-1], ..., a[0] and b[k-1], ..., b[0], return k+1
          bits s[0], ... , s[k]
docstring_tokens: Add the bits a [ k - 1 ] ... a [ 0 ] and b [ k - 1 ] ... b [ 0 ] return k + 1 bits s [ 0 ] ... s [ k ]
function: def BitAdd(a, b, bits_to_compute=None):
      """ Add the bits a[k-1], ..., a[0] and b[k-1], ..., b[0], return k+1
          bits s[0], ... , s[k] """
      k = len(a)
      if not bits_to_compute:
          bits_to_compute = range(k)
      d = [None] * k
      for i in range(1,k):
          #assert(a[i].value == 0 or a[i].value == 1)
          #assert(b[i].value == 0 or b[i].value == 1)
          t = a[i]*b[i]
          d[i] = (a[i] + b[i] - 2*t, t)
          #assert(d[i][0].value == 0 or d[i][0].value == 1)
      d[0] = (None, a[0]*b[0])
      pg = PreOpL(carry, d)
      c = [pair[1] for pair in pg]
      
      # (for testing)
      def print_state():
          print 'a: ',
          for i in range(k):
              print '%d ' % a[i].value,
          print '\nb: ',
          for i in range(k):
              print '%d ' % b[i].value,
          print '\nd: ',
          for i in range(k):
              print '%d ' % d[i][0].value,
          print '\n   ',
          for i in range(k):
              print '%d ' % d[i][1].value,
          print '\n\npg:',
          for i in range(k):
              print '%d ' % pg[i][0].value,
          print '\n    ',
          for i in range(k):
              print '%d ' % pg[i][1].value,
          print ''
      
      for bit in c:
          pass#assert(bit.value == 0 or bit.value == 1)
      s = [None] * (k+1)
      if 0 in bits_to_compute:
          s[0] = a[0] + b[0] - 2*c[0]
          bits_to_compute.remove(0)
      #assert(c[0].value == a[0].value*b[0].value)
      #assert(s[0].value == 0 or s[0].value == 1)
      for i in bits_to_compute:
          s[i] = a[i] + b[i] + c[i-1] - 2*c[i]
          try:
              pass#assert(s[i].value == 0 or s[i].value == 1)
          except AssertionError:
              print '#assertion failed in BitAdd for s[%d]' % i
              print_state()
      s[k] = c[k-1]
      #print_state()
      return s
function_tokens: def BitAdd ( a , b , bits_to_compute = None ) : k = len ( a ) if not bits_to_compute : bits_to_compute = range ( k ) d = [ None ] * k for i in range ( 1 , k ) : #assert(a[i].value == 0 or a[i].value == 1) #assert(b[i].value == 0 or b[i].value == 1) t = a [ i ] * b [ i ] d [ i ] = ( a [ i ] + b [ i ] - 2 * t , t ) #assert(d[i][0].value == 0 or d[i][0].value == 1) d [ 0 ] = ( None , a [ 0 ] * b [ 0 ] ) pg = PreOpL ( carry , d ) c = [ pair [ 1 ] for pair in pg ] # (for testing) def print_state ( ) : print 'a: ' , for i in range ( k ) : print '%d ' % a [ i ] . value , print '\nb: ' , for i in range ( k ) : print '%d ' % b [ i ] . value , print '\nd: ' , for i in range ( k ) : print '%d ' % d [ i ] [ 0 ] . value , print '\n   ' , for i in range ( k ) : print '%d ' % d [ i ] [ 1 ] . value , print '\n\npg:' , for i in range ( k ) : print '%d ' % pg [ i ] [ 0 ] . value , print '\n    ' , for i in range ( k ) : print '%d ' % pg [ i ] [ 1 ] . value , print '' for bit in c : pass #assert(bit.value == 0 or bit.value == 1) s = [ None ] * ( k + 1 ) if 0 in bits_to_compute : s [ 0 ] = a [ 0 ] + b [ 0 ] - 2 * c [ 0 ] bits_to_compute . remove ( 0 ) #assert(c[0].value == a[0].value*b[0].value) #assert(s[0].value == 0 or s[0].value == 1) for i in bits_to_compute : s [ i ] = a [ i ] + b [ i ] + c [ i - 1 ] - 2 * c [ i ] try : pass #assert(s[i].value == 0 or s[i].value == 1) except AssertionError : print '#assertion failed in BitAdd for s[%d]' % i print_state ( ) s [ k ] = c [ k - 1 ] #print_state() return s