|Portada|Blog|Wiki|

######## OPERATIONS ON BINARY NUMBERS ########

======== UNSIGNED ARITHMETIC ========

Given binary numbers on the standard input, ie: 42 and 23 as 101010 and 10111.
We will create on this section a basic calculator. The first process is to
group the operations according to their precedence and left associativity:

echo '10+101010*10111*11' | sed '...' -> '10+(101010*10111)*11'

Since we don't have the expressive power of context free grammars we cannot
easily place all the parentheses, yet a single pair for a single operation is
enough, since we can go back to :i to add another pair of parentheses.

sed ':i
     s,[0-9]\+[*/][0-9],(&),; tm
     s,[0-9]\+[+-][0-9],(&),; ta
     q'

For the addition we need an extended addition table:
  (x0+y0) -> (x+y)0
  (x0+y1) -> (x+y)1
  (x1+y0) -> (x+y)1
  (x1+y1) -> (x+y)c0    # Here we carry one,
Thus we extend the table of substitutions with:
  (x0+y0)c -> (x+y)1
  (x0+y1)c -> (x+y)c0
  (x1+y0)c -> (x+y)c0
  (x1+y1)c -> (x+y)c1
And a final one, cleaning up:
  (+)c -> 1
  (+)  -> 
Remembering that this wouldn't work unless we add any leading zeros as needed.

sed 'a:
     s_(+\([01]\)_(0+\1_
     s_\([01]\)+)_\1+0)_
     s_(\(.*\)0+\(.*\)\([01]\))_(\1+\2)\3_
     s_(\(.*\)1+\(.*\)0)_(\1+\2)1_
     s_(\(.*\)1+\(.*\)1)_(\1+\2)c0_
     s_(\(.*\)0+\(.*\)0)c_(\1+\2)1_
     s_(\(.*\)0+\(.*\)1)c_(\1+\2)c0_
     s_(\(.*\)1+\(.*\)0)c_(\1+\2)c0_
     s_(\(.*\)1+\(.*\)1)c_(\1+\2)c1_
     s_(+)c_1_
     s_(+)__
     ta
'
                                                                               π