/dev/code

I have an odd fascination with binary clocks. I just recently built my own, based on an AVR microcontroller, which I will post more about soon. I also have a binary watch that was a present from Ceal a few years ago. During a particular boring meeting yesterday, I was watching it count the seconds, and I realized that to increment a binary number by 1, you are really looking for the pattern: 01*$ (the last part of the number consisting of 0 followed by only 1s to the end of the line). When you find that pattern, you just invert the bits.

For example, to add 1 to 10011 (19 decimal), you are only interested in the 011 at the end. You invert that part and get 10100 (20 decimal). The only time the 01*$ pattern doesn't work is when the number is all 1s. In that case, you can insert a leading 0 and again just invert the bits. For example, 1111 (15 decimal) first becomes 01111, then inverted becomes 10000 (16 decimal).

So, after that little epiphany, I began to wonder if I could write a sed script that functioned as a binary adder. At first I didn't think it could be done, because I was thinking purely in terms of doing substitutions. I have since learned much more about the capabilities of sed and found it was possible. Here is the script, along with an explanation of what each line does:


s/^1*$/0&/
h
s/\(.*\)01*$/\1/
x
s/^.*\(01*\)$/\1/
y/01/10/
x
G
s/\n//


s/^1*$/0&/	If the number is all 1s, insert a leading 0
h	Copy the current line to the hold buffer
s/\(.*\)01*$/\1/	Strip off the 01*$ pattern from the end
x	Exchange the current pattern with the hold buffer
s/^.*\(01*\)$/\1/	Strip off everything but the 01*$ pattern
y/01/10/	Invert the bits in the current line
x	Exchange the current pattern with the hold buffer (go back to the prefix bits)
G	Join the hold buffer (the end bits that were just inverted) to the current pattern (sed puts it on a separate line)
s/\n//	Join the two lines

To test this, I wrote a little script that starts with 0, runs it through the adder, prints the result, and the runs the result through the adder. This is the script (caution, it loops forever):


#!/bin/sh
NUM=0
while true; do
NUM=`echo $NUM | sed -f adder.sed`
echo $NUM
done


And here is a snippet of the results:

1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111
10000
10001
10010
10011
10100