1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Why not pick up a textbook on computer architecture? $\endgroup$ – Yuval Filmus Feb 5 at 19:54
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I count 3 logical primitives there (AND, OR, NOT). The OP asked for AND + NOT or OR + NOT. $\endgroup$ – a1s2d3f4 Feb 8 at 16:12
  • $\begingroup$ Right. Indeed, thanks to de Morgan Theorem, this is equivalent. It is possible replace all a&b by ~(~a|~b). It is systematic, but does not improves readability... Updated the answer. $\endgroup$ – Alain Merigot Feb 8 at 20:29
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.