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.