is bitwise AND operator transitive in C and C++?

Question

I have a question: Is bitwise anding transitive, particularly in C and C++?

Say res=(1 & 2 & 3 & 4), is this same as res1=(1&2) and res2=(3&4) and res= (res1 & res2). Will this be same?

Answer 1

Yes, bitwise AND is transitive as you've used the term.

It's perhaps easier to think of things as a stack of bits. So if we have four 4-bit numbers, we can do something like this:

A = 0xB;
B = 0x3;
C = 0x1;
D = 0xf;

If we simply stack them up:

A    1 0 1 1
B    0 0 1 1
C    0 0 0 1
D    1 1 1 1

Then the result of a bitwise AND looks at one column at a time, and produces a 1 for that column if and only if there's a 1 for every line in that column, so in the case above, we get: 0 0 0 1, because the last column is the only one that's all ones.

If we split that in half to get:

A    1 0 1 1
B    0 0 1 1
A&B  0 0 1 1

And:

C    0 0 0 1
D    1 1 1 1
C&D  0 0 0 1

Then and those intermediate results:

A&B 0 0 1 1 
C&D 0 0 0 1
End 0 0 0 1

Our result is still going to be the same--anywhere there's a zero in a column, that'll produce a zero in the intermediate result, which will produce a zero in the final result.

Answer 2

The term you're looking for is associative. We generally wouldn't call a binary operator "transitive". And yes, & and | are both associative, by default. Obviously, you could overload the operators to be something nonsensical, but the default implementations will be associative. To see this, consider one-bit values a, b, and c and note that

(a & b) & c == a & (b & c)

because both will be 1 if and only if all three inputs are 1. And this is the operation that is being applied pointwise to each bit in your integer values. The same is true of |, simply replacing 1 with 0.

There are also some issues to consider if your integers are signed, as the behavior is dependent on the underlying bit representation.