What is considered arithmetic when dealing with bits?

Question

In a recent homework question we were asked to implement a program that would use only bitwise operations. From our notes, this includes & | ^ ~ >> << and >>>. We are not allowed to use arithmetic operations, or loops.

Since immediately addition can be defined with the above accepted operators, what constitutes "arithmetic"? Would unary operations be allowed?

For example, I could define incrementation and decrementation using ~ and the unary -, and recursively call both until the decremented number reached 0, meaning both numbers were added (think addition in brainfuck). Is this arithmetic?

Answer 1

A program that uses only bitwise operations is just that – a program which only uses bitwise operations. Bitwise operations are universal, that is, you can define any function using them. What makes things interesting is that we care about the complexity of implementing a given function using only bitwise operations.

In particular, suppose that we only care about the complexity up to multiplicative constants (i.e. we only care about the big O). Any operation which can be implemented using a constant number of bitwise operations is admissible – the resulting notion of complexity is the same (up to multiplicative constants). So if you can implement addition using a constant-size formula, then you are welcome to use addition.

The constraint doesn't mean that at no point of your program are you allowed to compute by chance some arithmetic function – it just means that the basic operations you are allowed are only the bitwise ones.