World's most popular travel blog for travel bloggers.

What is considered arithmetic when dealing with bits?

, , No Comments
Problem Detail: 

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?

Asked By : spyr03
Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback