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

Question

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?

Thanks in advance.

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)

Answer 1

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.

Answer 2

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.

Answer 3

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?

Answer 4

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.