Search code examples
bit-manipulationbitwise-operatorsarithmetic-expressionsinteger-arithmeticbitwise-and

AND bitwise operation over addition


I've been looking for a while now about this issue, yet I couldn't find any result. assuming A, B and C are integers, is there a function (arithmetic or boolean) F and G such that:

(A + C)&(B + C) = F(A,B) + G(C)

where & is the bitwise operator AND. in other word i'm looking for a way to get the C value to be independent of A and B.

Edit the "+" here is the ordinary plus operation not OR.


Solution

  • No.

    Let's consider the case that A = 0, and B and C are chosen from 0 and 1. Here's the resulting table:

    B C  output
    0 0  0
    0 1  1
    1 0  0
    1 1  0
    

    Then we ask the question, are there functions F and G such that F(B) + G(C) == C & (B + C). There can be no solution, because the first two rows imply that G(1) = G(0) + 1 (the contribution from F cannot change, because its argument is zero both times), and the bottom two rows imply that G(0) = G(1) (again because the contribution from F cannot change, its argument is one both times). And we can't have it both ways, G(1) = G(0) + 1 and G(0) = G(1) cannot both hold.

    There are other cases than A = 0 and B and C both binary, but if F and G cannot exist in one case then all the other cases cannot "fix" that.