######## 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
'