# Expressing bitwise operations in terms of other functions

I'm asking in the spirit of these two questions: can bitwise operations (AND, OR, XOR) be expressed in terms of other (more familiar?) functions?

I had been playing around with the bitwise operations in Mathematica a while back, and was at first struck by this identity for bitwise NOT: ~ n == -1 - n (I'll use C-ish notation/syntax for this question, but I'm using Mathematica's definitions, which assume a two's complement representation for negative integers.)

Try as I might, I have not managed to figure out alternative ways of expressing the other bitwise operations. I have also tried Using The Fabulous Search Engine to see if other people have looked into this, but I probably am not using the right keywords.

I have noticed that the implementation of the bitwise operators in Mathematica satisfies de Morgan's theorem:

i | j == -1 - ((-1 - i) & (-1 - j))

i & j == -1 - ((-1 - i) | (-1 - j))


and the following identity for bitwise XOR is satisfied as well:

i ^ j == (i | j) & (-1 - (i & j))


I suppose then that any alternate expression for the bitwise operators would have to satisfy these identities as well.

(I am not intending to replace the bitwise expressions in actual programming, of course; they are already optimized, and there is really no practical reason to replace them with "more mathematical" expressions. I am asking merely for curiosity's sake.)

References and sundry information will be appreciated.

-
I don't know of any other more appropriate tags; please retag if you can think of anything more appropriate. – J. M. Dec 22 '10 at 3:56
Would a polynomial interpolation, e.g. of the bitwise operations between two bytes, be pertinent? – hardmath Dec 22 '10 at 4:19
@hardmath: It doesn't look to me that polynomial interpolation would be appropriate here; I feel that any interpolant that works for $n$ or so pairs (for large enough $n$) would fail spectacularly for pairs just a bit outside that range. – J. M. Dec 22 '10 at 4:36
Exclusive OR is addition in $\mathbb{Z}_2^n$. The AND operation corresponds to set intersection, OR to set union, NOT to complementation (and XOR to symmetric difference).
 I may have not expressed myself clearly; I mentioned that bitwise NOT can be re-expressed as $-1-n$ ; are there similar "identities" for the other bitwise operations? – J. M. Dec 22 '10 at 5:24