Thursday, May 22, 2008

 

Adding 1 to a binary number in sed

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
hCopy the current line to the hold buffer
s/\(.*\)01*$/\1/Strip off the 01*$ pattern from the end
xExchange 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
xExchange the current pattern with the hold buffer (go back to the prefix bits)
GJoin 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

Comments:
# bash binary ripple counter
NUM=0
while [ $NUM -lt 1000 ]
do
NUM=$NUM^
while echo $NUM | fgrep -q '^'
do
echo; echo -n $NUM
NUM=`echo $NUM | sed -e '
s/1^/^0/
t
s/^^/1/
t
s/0^/1/'`
done; echo; echo -n $NUM = $((2#$NUM)).
done; echo
 
Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?