Conditional Using Bitwise Operators

Question

How is the conditional operator represented using bitwise operators?

It is a homework question where I have to implement the conditional operator using only bitwise operations. It would be simple if if statements were allowed, however it has to be strictly bitwise operators.

Only the operators !, ~, &, ^, |, +, >>, and << can be used. No if statements or loops can be used.

The function takes three ints and works just like the normal conditional operator. The first argument is evaluated as either zero or non-zero. If the first argument is zero then the second argument is returned. If the first argument is non-zero then the third argument is returned.

I was hoping there would be a simple algorithm for this. Any ideas on where to start would be a great help.

Answer 1

It's not, basically. The conditional operator will only evaluate one of the second or third operands; bitwise operators always evaluate both operands.

I don't think it really makes sense to think of the conditional operator in terms of bitwise operators to start with... for example, if the second and third operands are pointer types, you wouldn't want to think of those in terms of bitwise ops, would you? Treat the conditional operator separately to the bitwise operators - you won't do yourself any favours by trying to amalgamate them.

Answer 2

Are shifts allowed as bitwise operators? Are arithmetic operators allowed?

Your edit is not entirely clear, but I assume that you need to implement an equivalent of

a ? b : c

where a, b and c are integers. This is in turn equivalent to

a != 0 ? b : c

One way to achieve that is to find a way to turn non-zero value of a into an all-ones bit pattern using only bitwise operators. If we figure out how to do that, the rest would be easy. Now, I don't immediately remember any ingenious tricks that would do that (they do exist I believe), and I don't know for sure which operators are allowed and which are not, so for now I will just use something like

a |= a >> 1; a |= a >> 2; a |= a >> 4; a |= a >> 8; a |= a >> 16;
a |= a << 1; a |= a << 2; a |= a << 4; a |= a << 8; a |= a << 16;

For a 32-bit integer type, if (and only if) there was at least one bit set in the original a, the above should result in all bits of a set to 1. (Let's assume we are working with unsigned integers, to avoid the issues associated with shifting of signed values). Again, there must be a more clever way to do that, I'm sure. For example: a = !a - 1, but I don't know if ! and - are allowed.

Once we've done that, the original conditional operator becomes equivalent to

(a & b) | (~a & c)

Done.