10

Nand is known as a 'universal' logic gate, because it allows you define all other boolean logic gates:

not(x) = nand(x,x)
and(x, y) = not(nand(x, y))
or(x, y) = nand(not(x), not(y))
nor(x, y) = not(or(x, y))
xor(x, y) = nand(nand(a, nand(a, b)), nand(b, nand(a, b)))

This is known as nand-logic, and is commonly used in modern computers because a transistor can be made to behave just like a nand-gate.

I am wondering if it is possible to do something similar with the bitwise operations. Can an e.g. bitwise nand (bnand) be used to define bnot, bor, band, bnor, bxor? Is there an universal bitwise operation?

Improve this question

2 Answers 2

Reset to default
13

On a hardware level there is no difference between bitwise and logical. So, yes. A logical operation is just a bitwise operation on a single bit.

Improve this answer
2

On most modern microprocessors the bitwise operations are implemented natively, so that there is no benefit of having a NAND operation.

For example the x86 instruction set has: AND, OR, XOR, NOT. These all are performed in one single cycle as far as I know, so that there would be no benefit by replacing them with several NAND operations. It also has ANDN which is an equivalent for ((NOT x) AND y) that could be generated by a clever optimization compiler to gain a cycle.

The RISC movement tried to promote reduced instruction set for a simpler an more performant architecture. The idea was that compilers would have to combine simpler and faster instructions. It appears however that apart from some experimental or teaching processors, most provide natively NAND as well as the usual bitwise operations (e.g. PowerPC or ARM).

Improve this answer
3
  • I am genuinely not sure how boolean operators are implemented in CPUs these days, but it used to be fairly common to use a 4-to-1 mux, feeding in "the truth table" as the 4 inputs, then use the two bits to operate on as the selector for the output. Gives you a single circuit that can be used for all 16 two-operand boolean functions.
    – Vatine
    Sep 1, 2016 at 10:21
  • 2
    The fact that OR, XOR and NOT are implemented "natively"and take no more than a single clock cycle says nothing about whether they are build using only NAND circuits or nor. I suspect they are build using only NANDs these days because transistors are really cheap and really fast. Vatine's 4-to-1 method is optimized for using a small number of transistors, which is pointless in the nanometer era.
    – Martin Maat
    Sep 1, 2016 at 17:29
  • RISC has been rendered meaningless by time. When it emerged, typical complex instructions took multiple clock cycles, like 10 or so. And this was not about OR/AND/NOT, these were already quick and considered "simple" and essential for any CPU so they would certainly not be dropped by a RISC processor. Today, complex instructions take less then a clock cycle (due to pipelining and multi-threading/multi-core.
    – Martin Maat
    Sep 1, 2016 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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