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.
$\begingroup$
$\endgroup$
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.
answered Feb 1 '19 at 19:33
-
$\begingroup$ Thank you, now I see I got a little bit narrow-minded with this topic ;) $\endgroup$ – B.Nary Feb 1 '19 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 '19 at 17:55
$\begingroup$
$\endgroup$
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
