11
$\begingroup$

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)

  • 7
    Bitwise AND is already a mathematical operation.2011-05-08
  • 0
    Yeah I know but I want an operation that works directly on Integers2011-05-08
  • 0
    Are you sure you want integers and not natural numbers instead?2011-05-08
  • 6
    Bitwise AND already works directly on integers.2011-05-08
  • 0
    Unless you define a grammar of "integer operations" you can just dismiss any answer given.2011-05-08
  • 0
    Yeah. Good point. I'm sorry, if we puts negative numbers into this we have to deal with 2's complement, and I don't think I need that. Thanks.2011-05-08
  • 0
    I feel that this question should do better on a programming related site, perhaps SO. I'm voting to close as off topic.2011-05-08
  • 0
    I want to say that while the OP has some confusion on the definition of a mathematical operation, it is a valid question to ask for a "simpler" description and I think that it can be productive to answer this kind of question as it is the kind of question that can lead to better understanding.2011-05-08
  • 0
    @Asaf Karagila: I doubt it. If there *were* the kind of "basis-free" formula the OP is looking for, we would probably know it.2011-05-08
  • 0
    @Felipe, You have given a grammar "+,-,/,pow(base,exp)" which includes formulas like "x+y/pow(x+x,y)" and excludes things like "sin(x)+y" (and a trillion other things..) so potentially you could prove that $f$ I defined cannot be realized as a function of this grammar but as I said that would probably be extremely different (I see no obvious way to prove it).2011-05-08
  • 0
    @Felipe, that "sharper" version of this question might be worth asking but I would be surprised if anyone could answer it.2011-05-08
  • 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)2011-05-08
  • 0
    @Felipe, one might be able to show a certain set of numbers is "definable" in terms of $f$ and the grammar, which is not definable just by the grammar. The definition of "definable" comes from model theory (part of logic).2011-05-08
  • 0
    @Felipe, for example an extremely fast growing function is definable using exponentials that is not definable using just addition and multiplication -- so exponentials can't be defined using addition and multiplication (you need something like recursion too). Perhaps some aspect of $f$ could be found that is not definable in terms of the grammar.2011-05-08
  • 3
    possible duplicate of [Expressing bitwise operations in terms of other functions](http://math.stackexchange.com/questions/15141/expressing-bitwise-operations-in-terms-of-other-functions)2011-05-08
  • 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...2011-05-08
  • 0
    I vote against closing.2011-05-08

5 Answers 5

9

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.

  • 0
    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 =P2011-05-08
  • 0
    @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.2011-05-08
  • 0
    It should be the set of "Whole numbers" instead of "Natural numbers".2013-12-23
  • 0
    I think in Computer Science the two are generally considered equivalent (the Peano axioms define 0 to be part of the naturals for instance)2014-12-25
4

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.

  • 0
    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.2011-05-08
  • 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.2011-05-08
  • 0
    @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.2011-05-08
  • 0
    Agreed.123456782011-05-08
2

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?

  • 0
    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.2011-05-08
  • 2
    @Felipe what you have just described is a perfectly valid definition for the function you are looking for...2011-05-08
  • 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).2011-05-08
  • 0
    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...2011-05-08
  • 0
    @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_.2013-12-22
2

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.

2

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] $$