If you can represent/model a Conditional IF statement with AND + NOT or OR + NOT

Question

I am still trying to wrap my head around this, which shows how to simulate control-flow without using an if-statement.

I've been looking at basic logic today and learned that you can represent all logic with 1 (like NAND), 2 (AND + NOT, OR + NOT, etc.), or 3 logical primitives.

This makes me wonder if you can represent the if-statement using just AND + NOT or OR + NOT (and what it might look like), such that a program loop would be able to evaluate an expression such as if (a) b(), or something more complex like in the first link above.

Answer 1

This is partly possible.

Assume your code is

if (a==b)
  x = y;
else
  z = w;

where all vars are ints

This can be rewritten as

c = (a==b) -1 // true 1-1=0; false 0-1=0xfffffffff

x = (~c &  y) | (c & x); // or ~(~(~c&y)&~(c&x)) to only use & and ~
z = (c &  w) | (~c & z);

This can be applied to arbitrarily complex expressions, even nested, but you cannot have function calls, which seriously limits application area.

Note that this is routinely used to program SIMD extensions like SSE or AVX. In SIMD, you do several operations simultaneously and the only way to perform if-then-else if by mean of masking and anding/oring.

Similarly, there is the same problem on a GPU where hundred of processing elements work simultaneoulsy. It is hidden from the user, but internally the controller transforms if-then-else to logic ops. It even keeps track of it across function calls.

Answer 2

What you need is a multiplexer.

In a CPU "If" is evaluated using the ALU (To determine if the argument of "If" is 0), the result of which feeds the select line of a multiplexer. The inputs of the multiplexer are the two possible positions in the code you want to jump to. The output will be the position you do jump to.

You can build a multiplexer from a functionally complete set.

Note: Alain Merigot's solution uses 2 multiplexers.