Consider the following operations:
- Bitwise AND
- Bitwise OR
- Bitwise NOT
- Bitwise XOR
- Another bitwise operator like NAND or NOR
- Binary addition
- Binary subtraction
- Binary multiplication
- Binary division
- Binary left and right shifting
Many of these operations can be derived from each other. For example, only bitwise AND and NOT is enough to calculate bitwise XOR and OR, and binary subtraction can be used to calculate bitwise NOT and addition.
Now, what is the best way to implement all of these operations using a single one?
Notes:
- Assume a fixed, known number of bits
- Assume branching/looping is allowed, including the condition: is a >= 0
- Arithmetically, numbers are considered to be signed two's complement binary integers. Overflow is being ignored.
- These are integer operations so something like 5/2 will be calculated as 2
- I will add more important conditions if they are needed.
My main attempt included using bitwise NAND operation to try to derive the other operations; this made it easy to implement all the bitwise operators, but I was left stumped when I tried to implement addition. I foudn that it IS possible, but only with hardcoded bitmasks, forming a long and inefficient process. So, I tried using SUB instead, and easily derived a NOT gate and other arithmetic operators, but am having trouble deriving more important bitwise operators like AND and OR. Ideally I would like to avoid lookup tables or long hardcoded solutions, but I realize that may not be possible.