I wonder if there are more things we can do with bits aside from NOT, AND, OR, XOR operations? I got this question from my teacher and I'm not really sure. How about bit shifting ">>"? Could we count this? Thanks for replying.


If you think about it, there are $2^4 = 16$ possible ways of combining two bits to give a single-bit ouput (AND, OR, NOR, NAND, XOR, ...). Can you work out what they all are? This is because there are four possible input combinations ($00$, $01$, $10$, $11$) and any subset of those can be mapped to~$1$. But we could combine more than two bits to give a single bit output – can you work out how many operators there are that take $k$ bits as input and output one bit?

And we're not even restricted to one bit of output: in general, we can have any number of bits of input and any number of bits of output. You mentioned shifts, which map $k$ bits to $k$ bits, as an example of this.

Overall, there are infinitely many ways of combining bits.

  • $\begingroup$ Thank you, now I see I got a little bit narrow-minded with this topic ;) $\endgroup$ – B.Nary Feb 1 at 19:38
  • $\begingroup$ Ages ago, Windows had one graphic operation that combined four single bit inputs - 16 possible inputs, 65536 different functions. $\endgroup$ – gnasher729 Feb 2 at 17:55

Classifying the bit operations comes up when investigating special kinds of operations, like reversible bit operations or falsehood free (classical) logical operations.

Formally, a reversible gate is just a permutation $G : \{0, 1\}^k \to \{0, 1\}^k$ of the set of $k$-bit strings, for some positive integer $k$. The most famous examples are:

  • the 2-bit CNOT (Controlled-NOT) gate, which flips the second bit if and only if the first bit is 1;
  • the 3-bit Toffoli gate, which flips the third bit if and only if the first two bits are both 1;
  • the 3-bit Fredkin gate, which swaps the second and third bits if and only if the first bit is 1

In similar terms, a falsehood free logical operation is just a Boolean function $f : \{0, 1\}^k \to \{0, 1\}$ with $f(1, \ldots, 1) = 1$. Before starting to omit logical operations, one can try to list as many logical operations as barely reasonable:

If we limit ourself to constants, unary operations, and binary operations, then we get:

  • Constants for truth ($\top$) and falsehood ($\bot$)
  • An unary operation for negation ($\lnot$)
  • Binary operations for: or ($\lor$), and ($\land$), implication ($\to$), minus ($-$), nand ($|$), nor ($\overline{\lor}$), equivalence ($\equiv$), and xor ($\oplus$). The remaining binary operations add nothing new: reverse implication, reverse minus, first, second, not first, not second, true, and false

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.