# More bit stuff

Out of curiosity, I worked out the carry bit for the addition of two 8-bit symbolic words, a…a and b…b.

I intend to work out some method of intelligently re-collapsing common subexpressions.

For all I know, that’ll be a non-effective, circular endeavor; i.e. what I started with might be no more complex than whatever end result I come up with.

I am currently mucking around with what I call ‘tree expressions’: a complex expression gets reduced to a tree of

expression = symbol . primarySubTree | secondarySubtree

where symbol is an atomic symbolic bit (e.g. either ‘x’ or ‘!x’), and both primarySubTree and secondarySubTree don’t contain that symbol.

I.e. I first simplify the expression to a list of terms, each term a ‘flat’ list of symbolic factors.

a.b.c | a.b.!c | a.!b.d … | b.c.d | … or whatever

then find the most common symbol (e.g. a), and convert the expression to

a.(b.c | b.!c | !b.d…) | (b.c.d | …)

then repeat recursively on both subtree, until everything is either expressed as a tree or of a simpler form.

To get a feel for how re-collapsing would work: I let my program express the carry as a tree expression, then manually reduced the carry expression to (using lower case x, y, … for intermediate results):

```x = a.!b | !a.b
y = x.(a | b)
z = y.(a | b)
t = z.(a | b)
u = t.(a | b)
v = u.(a | b)
w = v.(a | b)
carry = a.b.w | a.b.v | a.b.u | a.b.t | a.b.z | a.b.y | a.b.x | a.b
```

which has a nice symmetry to it.

The ‘normal’ carry expressions work out as follows (using upper case X, Y,… for intermediate results):

```X = a.b
Y = a.b | X.(a.!b | !a.b)
Z = a.b | Y.(a.!b | !a.b)
T = a.b | Z.(a.!b | !a.b)
U = a.b | T.(a.!b | !a.b)
V = a.b | U.(a.!b | !a.b)
W = a.b | V.(a.!b | !a.b)
carry = a.b | W.(a.!b | !a.b)
```

which seems to be about the same complexity.

Note: If we write the XOR operator as ^, then a ^ b == (a.!b | !a.b)

This is the same, using the XOR operator:

```x = a ^ b
y = x.(a | b)
z = y.(a | b)
t = z.(a | b)
u = t.(a | b)
v = u.(a | b)
w = v.(a | b)
carry = a.b.w | a.b.v | a.b.u | a.b.t | a.b.z | a.b.y | a.b.x | a.b
```

The ‘normal’ carry expressions:

```X = a.b
Y = a.b | X.(a ^ b)
Z = a.b | Y.(a ^ b)
T = a.b | Z.(a ^ b)
U = a.b | T.(a ^ b)
V = a.b | U.(a ^ b)
W = a.b | V.(a ^ b)
carry = a.b | W.(a ^ b)
```

What I like about the new form is that it starts down from the high bits. If we read it in pseudocody words, it says:

– if both a and b are set there is a carry (a.b in the carry expression)
– else if a and b are clear there is no carry (x is 0, hence y, z,.. are all 0)
– else if a or b are set there is a carry (y is 1)
– else if a or b are set there is a carry (z is 1)

It’s not very exciting, and I don’t see any practical uses for it, but it’s satisfying to see that the program came up with a nice, symmetrical alternate expression for the carry.