Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Digital Design 101 with pythonic infinite bit width solution in Uncategorized category for Funny Addition by Albin
# This is a software implementation of how addition is usually done in hardware.
# It is based on the two's complement notation of binary numbers, i.e. the kind
# you're used to.
#
# The 1-bit "full adder" is a circuit which can add two one-bit numbers.
#
# A B R
# 0 0 0
# 0 1 1
# 1 0 1
# 1 1 0
#
# A "Carry" output is included since 1+1 = 10 which cannot be represented
# using a single result bit.
#
# A B Co R
# 0 0 0 0
# 0 1 0 1
# 1 0 0 1
# 1 1 1 0
#
# In order to be able to chain these together to add larger numbers,
# we also add a "Carry" input, from the nearest lower-order adder.
# This means we now add three single-bit values with a two-bit result.
#
# A B Ci Co R
# 0 0 0 0 0
# 0 0 1 0 1
# 0 1 0 0 1
# 0 1 1 1 0
# 1 0 0 0 1
# 1 0 1 1 0
# 1 1 0 1 0
# 1 1 1 1 1
#
# We can place an arbitrary number of these full-adder modules next to each other
# calculating in (nearly) parallel to add arbitrarily large numbers. If we want
# to add two 4-bit numbers, we use 4 single-bit full adders. The first Carry
# input is tied to zero and the last Carry output is the "overflow" flag of our
# 4-bit adder (i.e. the result requires 5 bits to represent fully, annd the
# Carry output represents the 5th bit).
#
# A3 B3 A2 B2 A1 B1 A0 B0
# | | | | | | | |
# Co ++---++ Ci Co ++---++ Ci Co ++---++ Ci Co ++---++ Ci
# ----+ +--------+ +--------+ +--------+ +--- 0
# +--+--+ +--+--+ +--+--+ +--+--+
# | | | |
# R3 R2 R1 R0
# Single-bit full adder
# Returns (co, r)
def bitadder(a, b, ci):
r = a ^ b ^ ci
co = (a & b) | (ci & (a | b))
return (co & 0x1, r & 0x1)
# Recursive implementation which adds the infinitely large numbers python can
# handle. That puts our limit at 999bits.
# The carry flag will always be folded into the result in the end,
# and the external caller will get co = 0.
def numadder(a, b, c):
if (a == 0 and b == 0 and c == 0): return (0, 0)
# Addition of the LSB (right-most bit)
(co_bit, r_bit) = bitadder(a & 0x1,
b & 0x1,
c & 0x1)
# Addition of the rest
(co_num, r_num) = numadder(a >> 1,
b >> 1,
co_bit)
# Put our added LSB back on the total sum
r_num = (r_num << 1) | r_bit
return (co_num, r_num)
def checkio(data):
'The sum of two integer elements'
a,b = data
(co, r) = numadder(a, b, 0)
return r
if __name__ == '__main__':
assert bitadder(0, 0, 0) == (0, 0), "Bits 0"
assert bitadder(0, 1, 0) == (0, 1), "Bits 1"
assert bitadder(0, 1, 1) == (1, 0), "Bits 2"
assert bitadder(1, 1, 0) == (1, 0), "Bits 3"
assert bitadder(0, 0, 1) == (0, 1), "Bits 4"
assert checkio([5, 5]) == 10, 'First'
assert checkio([7,1]) == 8, 'Second'
print('All ok')
Dec. 7, 2012
Comments:
