How many ANDs and ORs does it take... Low-level bitwhacking at its most fun. | Hacker News Reader

How many ANDs and ORs does it take... Low-level bitwhacking at its most fun.

research.swtch.com

64 pointsuriel8 comments

Right at the top of the page, the author remarks that for n<=4 the parity function (f(a,b,c,d) = a XOR b XOR c XOR d) requires a maximal number of AND/OR gates to compute. Later on, he mentions that someone else proved that this isn't true for very large n. Nowhere on the page does he say what the worst case actually is, though the tables indicate that there are three genuinely-different Boolean functions of 5 variables that need 28 gates.

So, what's the worst case for n=5?

It turns out (http://boolean-oracle.swtch.com/?q=x%2by%2bz%2bw%2bv+in+0,1,...) that one of those three functions is the one that's true if and only if either 0, or 1, or 3 of the five variables are TRUE. (The other two are slight variations on that theme.)

It would be interesting to know whether the worst-case functions for larger n have as much symmetry as the worst cases for n<=5. (I'd guess not.)

"...I believe no one had ever known that little fact."

I submit for your consideration the vast number of truth tables written and referenced by engineers of Boolean logic circuits over the last many decades.

His claim is that that any 5 variable function can be expressed with no more than 28 gates, which isn't obvious. While a vast number of truth tables have been written down over the last few decades, it's unlikely that anybody else actually wrote down all of them at once, and found the minimal formulas.

Using 0s and 1s is advantageous here because you can operate on the sum of a group of numbers. If the sum is greater than 0 then OR on the set is true, otherwise false. If the sum is exactly 1 then XOR on the set will be true, otherwise false. If the sum is the length of the set AND on the set will be true, otherwise false. Just sayin

Taking the sum is itself expensive, though (in terms of logical operations). I don't think that realization really buys you much of anything - in particular, the least significant bit of the sum is by definition the parity of the set, so calculating the rest of the sum will only increase the number of operations required.

"Taking the sum is itself expensive, though (in terms of logical operations)"

"the least significant bit of the sum is by definition the parity of the set, so calculating the rest of the sum will only increase the number of operations required"

Can you expand on these two statements please? Examining the sum seemed like a more elegant solution when thinking in terms of higher level languages but the extent of my knowledge ends there. I'd really like to understand how sums compare in terms of actual operations.

Well, at its base, sums are just extensions of Boolean operations. You can implement simple logic circuits which compute sums. You can check out http://en.wikipedia.org/wiki/Adder_%28electronics%29 for more information; it describes some simple (and not so simple) circuits for adding two binary numbers.

[...] after hearing the problem from Neil Sloane, who suggested it as a variant of a similar problem first studied by Claude Shannon.

It figures ;-)

The web site http://boolean-oracle.swtch.com lets you type in a Boolean expression and gives back the minimal formula for it.

Nice, thanks. I'd suggest adding that example inputs can be had from the column at right (took me a bit to notice).

Reply on news.ycombinator.com