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

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):

And here is a snippet of the results:

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