# Is there any mathematical operation on Integers that yields the same result as doing bitwise “AND”?

I'll provide a little bit of a background so you guys can better understand my question:

Let's say I have two positive, non-zero Binary Numbers.(Which can, obviously, be mapped to integers)

I will then proceed onto doing an "AND" operation for each bit, (I think that's called a bitwise operation) which will yield yet another binary number.

Ok. Now this new Binary number can, in turn, also be mapped to an Integer.

My question is: Is there any Integer operation I can do on the mapped Integer values of the two original binary numbers that would yield the same result?

EDIT : I forgot to mention that What I'm looking for is a mathematical expression using things like +,-,/,pow(base,exp) and the like. I'm not 100% sure (I'm a compuer scientist) but I think what I'm looking for is an isomorphism.

LAST EDIT: I think this will clear any doubts as to what sort of mathematical expression I'm looking for. I wanted something like:

The bitwise AND of two Integers A and B is always equal to (AB)X(B)X(3).


The general feeling I got is that it's not possible or extremely difficult to prove(either its validity or non-validity)

-
Bitwise AND is already a mathematical operation. – Qiaochu Yuan May 8 '11 at 19:18
Bitwise AND already works directly on integers. – Asaf Karagila May 8 '11 at 19:25
(and you probably know this by now but "mathematical expression" is not a good term for the sort of grammar you gave, "calculator expression" would make more sense) – quanta May 8 '11 at 19:50
possible duplicate of Expressing bitwise operations in terms of other functions – J. M. May 8 '11 at 19:56
@quanta: "What I'm looking for is a mathematical expression using things like +,-,/,pow(base,exp) and the like." - more or less what I was asking in the other question. Anyway... – J. M. May 8 '11 at 20:00

Two important sets:

• The set of natural numbers $\mathbb N = \{0,1,2,3,4,\ldots\}$

• The set of binary sequences $\{0,1\}^* = \{\langle \rangle,\langle 0 \rangle,\langle 1\rangle,\langle 00\rangle,\langle 01\rangle,\langle 10\rangle,\langle 11\rangle,\langle 000\rangle,\ldots\}$

There is a function $\text{binary} : \mathbb N \to \{0,1\}^*$ which converts natural numbers to binary sequences, for example:

• $\text{binary}(0) = \langle 0\rangle$
• $\text{binary}(3) = \langle 11\rangle$
• $\text{binary}(5) = \langle 101\rangle$
• $\text{binary}(136) = \langle 10001000\rangle$

And it has a (left) inverse (since it is injective) that converts binary strings back to natural numbers $\text{binary}^{-1} : \{0,1\}^* \to \mathbb N$.

So you have a function $\text{and} : \{0,1\}^* \to \{0,1\}^*$ defined bitwise (presumably that means inductively defined on the length of binary strings). For example:

• $\text{and}(\langle 11\rangle,\langle 101\rangle) = \langle 001\rangle$

One can define now the function $f(x,y) = \text{binary}^{-1}(\text{and}(\text{binary}(x),\text{binary}(y)))$ which acts for example

• $f(3,5) = 1$

If you doubt any of this is "mathematical" you should specify what foundation you use (set theory probably?) and we can turn everything into axioms. If you wanted a formula like $f(x,y) = x^y - \frac{y+x}{y^{\sqrt{x}}}$ then I would guess no such thing exists but to prove you would have to define a specific grammar of formulas and it would be very difficult even then.

Although, for all $a,b$, $f$ satisfies the odd property $f(a,b) \le a$ and $f(a,b) \le b$. It may be possible to show no polynomials satisfy this property but I can't see how to do it for exponentials.

-
 Thanks for all the comments. Perhaps the "sharper"version which you mentioned would be something like "Is there an arithmetic expression which simulates that?"? Sorry for my terminology, I'm a computer scientist most of the time =P – Felipe Almeida May 8 '11 at 19:57 @Felipe, I have added an observation that might be able to prove that no polynomial can realize $f$ but it is not clear how to show that the basic arithmetic operations including exponentials are unable to define it. – quanta May 8 '11 at 20:05

One way to do a bitwise AND would be to decompose each integer into a sequence of values in {0,1}, perform a Boolean AND on each pair of corresponding bits, and then recompose the result into an integer. A function for getting the $i$-th bit (zero-indexed, starting at the least significant bit) of an integer $n$ could be defined as $f(n, i) = \lfloor n/2^i\rfloor \bmod 2$; the bitwise AND of two integers $m$ and $n$ would then be $$\sum_{i=0}^\infty (f(n,i) \mbox{ AND } f(m,i)) 2^i$$ Expressing the simpler Boolean AND in terms of common mathematical functions is left as an exercise to the reader.

-
That looks like what I've described in the title I guess. I know I can do it in that way. But I would like to know whether an expression using things like +,-,/, pow, whatever, that gave out the same results.. Perhaps I'm looking for an isomorphism, I'm not sure. – Felipe Almeida May 8 '11 at 19:32
@Felipe: you should say that in the OP (that you're looking for an expression using those symbols). If you want to use a fixed number of those symbols, I don't think this is possible. – Qiaochu Yuan May 8 '11 at 19:38
@Felipe: this comment explains a lot. Could you please add it (minus the last sentence) to your question? -> maybe indicating that this is an edit such that the answers so far don't seem to be wrong. – Fabian May 8 '11 at 19:39
Agreed.12345678 – Felipe Almeida May 8 '11 at 19:44

Note that this is an integer operation as you have defined it and it is a perfectly valid mathematical definition.

So you need to refine your question: You want a formula? What kind of formula would you accept?

-
Hmm.. I would like some function which, given two Integers as parameters, gave out another Integer Value, the same as what I would get if I first converted those 2 number to binary form, did a bitwise "and", and then re-converted it back to base 10 Integer. – Felipe Almeida May 8 '11 at 19:22
@Felipe what you have just described is a perfectly valid definition for the function you are looking for... – crasic May 8 '11 at 19:26
@crasic: I think he wants a function such that he doesn't have to convert to binary in the first place, saving computation and time (I think). – El'endia Starman May 8 '11 at 19:28
I'm actually not thinking in terms of time here, it just struck me that perhaps there was another way of reaching the bitwise AND computed value, without having to convert anything to binary form, just using the properties of natural numbers... – Felipe Almeida May 8 '11 at 19:34

If you have a bound on the size of the integers involved then you can find some polynomial whose values equal bitwise AND using Lagrange interpolation.

-