Conditional Statement using Bitwise operators

Go To StackoverFlow.com

9

So I see that this question has already been asked, however the answers were a little vague and unhelpful. Okay, I need to implement a c expression using only "& ^ ~ ! + | >> <<"

The expression needs to resemble: a ? b : c

So, from what I've been able to tell, the expression needs to look something like:

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

This works when a = 0, because anding it with b will give zero, and then the or expression will return the right side, (~a & c) which works because ~0 gives all ones, and anding c with all ones returns c.

However, this doesn't work when a > 0. Can someone try to explain why this is, or how to fix it?

2012-04-05 19:03
by atb


16

I would convert a to a boolean using !!a, to get 0 or 1. x = !!a.

Then I'd negate that in two's complement. Since you don't have unary minus available, you use the definition of 2's complement negation: invert the bits, then add one: y = ~x + 1. That will give either all bits clear, or all bits set.

Then I'd and that directly with one variable y & b, its inverse with the other: ~y & c. That will give a 0 for one of the expressions, and the original variable for the other. When we or those together, the zero will have no effect, so we'll get the original variable, unchanged.

2012-04-05 19:15
by Jerry Coffin
This is actually perfect. So why does adding one make all bit set or clear? I understand why that needs to happen, but I don't understand how that happens - atb 2012-04-05 19:22
If we started with 0, then flipping the bits gives all ones. When we add one, all those turn back to zeros (and the carry gets set, but we ignore it). If we started with 1, flipping the bits gives 111...10. Adding 1 turns that last 0 to a 1, so all the bits are now 1's - Jerry Coffin 2012-04-05 19:24
the y = ~x + 1 part got me confused; I finally figured it works due to integer overflow in case when x = 0, but it's not obvious.

The more clear solution for me was to first shift lsb to msb with left shift (00000001 => 10000000) and then copy msb with right shift: y = (x << 31) >> 31Anton Sergeyev 2017-09-04 20:48



3

In other words, you need a to have all bits set to 0, if a is false (i.e. 0), and have all bits set to 1, if a is true (i.e. a > 0).

For the former case, the work is already done for you; for the latter -- try to work out result of the expression ~!1.

2012-04-05 19:09
by George Skoptsov
well that's what I thought at first. ~!1 would give all ones which is perfect. However, if I were to do ~!a, and a = 0, then ~!0 would give me 1110, so I'm not sure what to do from here / - atb 2012-04-05 19:13
Ads