Thursday, May 29, 2008

NOT Puzzle Solution

Edited 2012/08/16: Updated problem attribution.

Last week, I closed with a puzzle: "Invert three inputs using only two NOT gates." I should start off by pointing out that I cannot take credit for this problem; it dates back to at least the 70s and was featured in HAKMEM by Richard Schroeppel. I myself learned about it via Clive Maxfield. I'm also told that Guy Steele beat me to the generalization to n case, however I cannot verify this, and the solution presented here is entirely my own.

The solutions that follow are just two of many possible ways of looking at this. Structurally, they are by no means the simplest solutions, but I find them to be conceptually the simplest. If you haven't tried to solve the puzzle yet I heartily recommend it; it makes knowing the solution so much more rewarding if you have.

Solution for 3 inputs

My solution to this puzzle involves reasoning on the number of inputs with value '1'. If none of the inputs are 1s, then all the outputs must be, and vice versa. To do this, we create a set of temporary variables with the goal of knowing exactly how many inputs were 1.

3 := A ∧ B ∧ C
2or3 := (A ∧ B) ∨ (B ∧ C) ∨ (A ∧ C)
0or1 := ¬ 2or3
1 := 0or1 ∧ (A ∨ B ∨ C)
0or2 := ¬ (1 ∨ 3)
0 := 0or1 ∧ 0or2
2 := 0or2 ∧ 2or3

From here we can just build our outputs directly:

X = 0 ∨ (1 ∧ (B ∨ C)) ∨ (2 ∧ (B ∧ C))
Y = 0 ∨ (1 ∧ (A ∨ C)) ∨ (2 ∧ (A ∧ C))
Z = 0 ∨ (1 ∧ (A ∨ B)) ∨ (2 ∧ (A ∧ B))

Solution for n inputs

This proof sketch is for odd n. If n is even, just invert the last input directly with a NOT, and use this pattern for the first n-1.

As before, we are going to reason on how many inputs (I1 to In) were 1. For this we will use a bit more syntax: {a-b} means anywhere from a to b inputs (inclusive) were 1, and {a, b} means either a or b inputs were 1, with no other possibilities allowed. First, we can generate all the ranges ending in n directly:

{1-n} := (I1 ∨ I2 ∨ … ∨ In)
{2-n} := ((I1 ∧ I2) ∨ (I1 ∧ I3) ∨ … ∨ (In-1 ∧ In))

{n-n} := (I1 ∧ I2 ∧ … ∧ In)

Clearly, this doesn't need any NOTs. Next, we are going to make all the ranges starting in 0 and ending in an odd number:

{0-1} := ¬ {2-n}
{0-3} := ¬ {4-n}

{0-(n-2)} := ¬{(n-1)-n}

This requires (n-1)/2 NOT gates. Using these together, we can have variables for all the odd numbers of inputs directly:

1 := {0-1} ∧ {1-n}
3 := {0-3} ∧ {3-n}

n-2 := {0-(n-2)} ∧ {(n-2)-n}
n := {n-n}

Again, this doesn't require any NOTs. Lastly, we use one more NOT to let us get all the even values:

{0,2,4,…,(n-1)} := ¬ (1 ∨ 3 ∨ … ∨ n)

0 := {0-1} ∧ {0,2,4,…,(n-1)}
2 := {0-3} ∧ {0,2,4,…,(n-1)} ∧ {2-n}
4 := {0-5} ∧ {0,2,4,…,(n-1)} ∧ {4-n}

n-1 := {0,2,4,…,(n-1)} ∧ {(n-1)-n}

There! Now we have a variable for each possible number of inputs with value 1, so we can just plug in all possibilities to get our outputs:

O1 = 0 ∨ (1 ∧ (I2 ∨ I3 ∨ … ∨ In)) ∨ … ∨ (n-1 ∧ (I2 ∧ I3 ∧ … ∧ In))
O2 = 0 ∨ (1 ∧ (I1 ∨ I3 ∨ … ∨ In)) ∨ … ∨ (n-1 ∧ (I1 ∧ I3 ∧ … ∧ In))

On = 0 ∨ (1 ∧ (I1 ∨ I2 ∨ … ∨ In-1)) ∨ … ∨ (n-1 ∧ (I1 ∧ I1 ∧ … ∧ In-1))

As you have seen, this took a total of (n-1)/2 + 1 NOT gates. Since n is odd, (n-1)/2 + 1 = ⌊n/2⌋ + 1, and we're done! Whew, I wouldn't want to implement that.

1. I love this problem too. I don't want burst your bubble, but it dates back at least to 1972: it is item 19 in HAKMEM (
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html). Also, I believe that Guy Steele beat you to generalizing it to n inputs. I don't have a citation, but I remember discussing it with him when Hacker's Delight came out (ca. 2001).

1. Ahh, good to know. I've updated the attribution section to mention this.

Thanks for the HAKMEM link! There is some other very interesting content in there as well, and new to me. I'm going to have to dig in further.

2. This comment has been removed by the author.

3. I wonder which solution you discussed. If you can create three inverters from two, you can create a fourth inverter from any two of the resulting three. By repeating this, it's possible to produce an infinite supply of inverters from an original pair. It would also be possible to use different reduction tactics to minimize the number of and/or gates.

1. I'm not sure that that's true - at least, I cannot figure out how to make it work. The problem is that the input to the second NOT is built from the result of the first, which is not expressible with a black box that inverts three inputs in parallel. You'd have to find a structure that doesn't require the data dependency to be able to generalize it to n-from-2.

I have not been able to find any solutions as you described, but I did find http://www2.engr.arizona.edu/~srini/papers/Srini-Pulse-Inverter.pdf , which reduces the requirements to floor(log2(n))+1 inverters by converting the count of '1' inputs into a binary number and inverting that.