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