What kind of operations can we do with bits?

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.

• Thank you, now I see I got a little bit narrow-minded with this topic ;) Feb 1 '19 at 19:38
• Ages ago, Windows had one graphic operation that combined four single bit inputs - 16 possible inputs, 65536 different functions. Feb 2 '19 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