12
$\begingroup$

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.

  • 0
    I don't know of any other more appropriate tags; please retag if you can think of anything more appropriate.2010-12-22
  • 0
    Would a polynomial interpolation, e.g. of the bitwise operations between two bytes, be pertinent?2010-12-22
  • 0
    @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.2010-12-22
  • 0
    Why do you want a "conventional" representation? What good will it do?2010-12-22
  • 0
    @Yuval: "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.", as I said.2010-12-22
  • 2
    @J.M: I was also inquisitive about this specific thing,here is an nice discussion (that rested my confusion):http://answers.google.com/answers/threadview/id/389777.html2010-12-22
  • 2
    @Deb: The discussion there seems to be for fractions; here, I am considering bitwise operations on integers.2010-12-22
  • 1
    @J.M.: Note that the formula -1-n for bitwise NOT(n) involves an identity of machine representations rather than of integers, inasmuch as the machine representation of "-1" in twos-complement is the integer $2^w-1$ for suitable word size w. Hence that formula relies on a fixed word size and limited range of values.2010-12-22
  • 1
    @hardmath: I'm aware that such limitations exist in C and other such languages; I got curious on how *Mathematica* did it with this snippet: "Bitwise operations in Mathematica in effect allow integers to have an unlimited number of digits. When an integer is negative, it is taken to be represented in two's complement form, with an infinite sequence of ones on the left. This allows `BitNot[n]` to be equivalent simply to $-1-n$"2010-12-22
  • 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!2010-12-22

3 Answers 3