```|Portada|Blog|Space|
```
```######## 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'

(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_(+\(\)_(0+\1_
s_\(\)+)_\1+0)_
s_(\(.*\)0+\(.*\)\(\))_(\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
'```
```document.title="wiki: sed/operations-on-binary-numbers"
```