Are 'addition' and 'bitwise or' the same in this case?

Question

Say I have four 32-bit numbers, defined so that their bits don't overlap, i.e.

unsigned long int num0 = 0xFF000000;
unsigned long int num1 = 0x00FF0000;
unsigned long int num2 = 0x0000FF00;
unsigned long int num3 = 0x000000FF;

Where in each number one could have anything in the place of the FFs.

Am I right in saying that addition and bitwise or would always produce the same output for such sort of numbers?

Thanks!

Solution 1

as long as for two numbers num1 and num2 applies num1 & num2 == 0, then follows:

num1 + num2 == num1 | num2

the reason for this is, that addition is basically a bitwise XOR, plus carry bit. But as long as there are no carry bits (num1 & num2 == 0) then addition boils down to bitwise XOR, which is (again because of num1 & num2 == 0) in this case logically equivalent to a bitwise OR

Solution 2

No:

num3 + num3 => 0x000001FE

num3 | num3 => 0x000000FF

Of course, as long as you ensure that you only add things together where you know that they don't have the same bits set, you should be safe.

Solution 3

Yes, as (seen bitwise) 0+1 is the same as 0|1. The only difference is 1|1 (=1) vs. 1+1(=0b10), i.e. create a 0 and having overflow, affecting the bits to the left).

So in your case both are equivalent. But you should go to the safe side and choose the less error-prone one.

Solution 4

As long as you're not doing something like num3 + num3, yes.

Solution 5

Whenever the bitwise addition adds more than one 1 (either because the sources have them, or the carry from another place is 1 too), then a carry is produced and one place affects the other. As long as in an addition there is at most one 1 added, things are the same as bitwise or.

This can also be seen when we look at the adder circuits (http://en.wikipedia.org/wiki/Adder_%28electronics%29), where when no carry is produced, all elements taking part in the circuit are the "or" elements.

View more solutions

Comments

[fredoverflow]

As a third alternative, you could also use exclusive-or, that is, the ^ operator.

[starblue]

But note that if you want to combine such numbers into one it is good style to use |.

[Jason]

wouldn't it be more accurate to say that addition is a bitwise XOR plus a carry?

[Albus Dumbledore]

Sorry, I forgot to implicitly exclude this case.

[not-a-user]

And because you will forget it again next time (everyone does) always use | for logical expressions. - In contrast to when you are really calculating, i.e. in cases where, say, the decimal representation also makes sense.

[Kyle Delaney]

Is one faster than the other?

[Andreas Grapentin]

@KyleDelaney the answer to that question does not fit into a comment box :)