Take the 2-minute tour ×
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.

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)

share|improve this question
6  
Bitwise AND is already a mathematical operation. –  Qiaochu Yuan May 8 '11 at 19:18
4  
Bitwise AND already works directly on integers. –  Asaf Karagila May 8 '11 at 19:25
1  
(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
2  
possible duplicate of Expressing bitwise operations in terms of other functions –  J. M. May 8 '11 at 19:56
1  
@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
show 12 more comments

5 Answers

up vote 8 down vote accepted

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.

share|improve this answer
    
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
    
It should be the set of "Whole numbers" instead of "Natural numbers". –  Mhenni Benghorbal Dec 23 '13 at 9:23
add comment

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.

share|improve this answer
    
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
1  
@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
add comment

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?

share|improve this answer
    
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
2  
@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
1  
@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
    
@FelipeAlmeida The point is that a function, canonically, is 'defined' by its values and not the operations to perform it. I suspect what you're after is something along the lines of an elementary function. –  Steven Stadnicki Dec 22 '13 at 23:34
add comment

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.

share|improve this answer
add comment

Indeed, the four bitwise operations (&, ^, !, |) can be represented as mathematical functions. This is probably not original data, but I haven't found it represented this way anywhere else on the Stack Exchange.

Let us start by finding the formula for x & y, the simplest of the four.

First, we need a way of comparing the bits of the two numbers, which must return $1$ if both numbers are $1$ and $0$ otherwise. Then, we will need a way to convert these numbers back into the binary, and by extension base $10$, result. The second is simple: multiplication of the two numbers. The third is also simple; we multiply each result by $2^n$ with an incremented $n$, and sum the results (exactly how binary numbers are formed). So already, we suspect that the formula will look something like:

$$ \sum_{n=0}^{b}2^n[f(x)][f(y)] $$

Where $b$ is the number of bits of which the number is composed, and $f$ yields the value of the $n$th decimal place when its argument is written in binary. Now, how can we reduce a number to its bits? Simple: we divide it by the same $2^n$ by which we later multiply, discard the remainder with the floor function, and do a modulo 2 operation to reduce the number to bits. So the final formula is:

$$ x\text{ & }y = \sum_{n=0}^{b}2^n\left(\left\lfloor\frac{x}{2^n}\right\rfloor \bmod 2\right)\left(\left\lfloor\frac{y}{2^n}\right\rfloor \bmod 2\right) $$

One would think that since multiplication is equivalent to a logical $\land$ AND, one need only change this formula to an addition-based format to gain the formula for x | y. However,

$$ \sum_{n=0}^{b}2^n\left[\left[\left(\left\lfloor\frac{x}{2^n}\right\rfloor \bmod 2\right) + \left(\left\lfloor\frac{y}{2^n}\right\rfloor \bmod 2\right)\right]\bmod 2\right] $$

does not yield OR, but XOR ^. This is because if both bits are $1$, they sum to $2$, and $2 \bmod 2 = 0$.

Now we can move to NOT. The operation to reverse bits is simple, $(x + 1) \bmod 2$. Building on the idea of how we obtain each bit from $\left\lfloor\frac{x}{2^n}\right\rfloor \bmod 2$, we find that !x is equivalent to:

$$ \sum_{n=0}^{b}2^n\left[\left(\left\lfloor\frac{x}{2^n}\right\rfloor \bmod 2 + 1\right) \bmod 2\right] $$

The last and most difficult of the four is OR. I will leave its derivation as an exercise to the reader, but the formula is

$$ x\text{ | }y = \sum_{n=0}^{b}2^n\left[\left[\left(\left\lfloor\frac{x}{2^n}\right\rfloor \bmod 2\right) + \left(\left\lfloor\frac{y}{2^n}\right\rfloor \bmod 2\right) + \left(\left\lfloor\frac{x}{2^n}\right\rfloor \bmod 2\right)\left(\left\lfloor\frac{y}{2^n}\right\rfloor \bmod 2\right)\bmod 2\right]\bmod 2\right] $$

share|improve this answer
add comment

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.