Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 4 down vote favorite

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.

share|improve this question
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
2  
@J.M: I was also inquisitive about this specific thing,here is an nice discussion (that rested my confusion):answers.google.com/answers/threadview/id/389777.html – Quixotic Dec 22 '10 at 6:29
1  
@Debanjan: Thanks for posting that Google Answers link. It's a write up I did... so many years ago that I would not have recalled doing so! – hardmath Dec 22 '10 at 13:32
show 5 more comments

1 Answer

up vote 1 down vote

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).

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.