Is there a general formula for the AND and OR bitwise operators?

Question

The bitwise operators AND and OR work as follows: "a AND b" is true if both A and B are true, and "a OR b" is false if both A and B are false. However, you can also preform these operations on numbers. If we represent "true" as "1" and "false" as "0", by converting a and b into binary, you can work out a AND b by comparing each binary digit and putting a 1 where both digits are 1, and work out a OR b by comparing each binary digit and putting a 0 where both digits are 0. The, the binary strings are converted back into decimal. I know how to work this out using the "column method" — writing the first binary number above the second and writing the answer underneath — but is there a formula I can use to plug in a and b and get a AND b? And, by extention, a formula for a OR b? Thanks in advance! (question edited for clarity)

Answer 1

Well, if you have positive integers $a,b$, it should be obvious how to chose $a_i,b_i\in \{0,1\}$ so that $a=\sum_i^\infty a_i 2^i$ and $b$ respectively.

Then you can compute $c_i= a_i+b_i\mod 2$ and get, hopefully that is want to see, $c=\sum_i^\infty c_i 2^i$, where the $c_i$ do not overlap.

Answer 2

Using the floor function $\lfloor x \rfloor$, which rounds $x$ down to the nearest integer, we can get the the $n$th binary digit (counting from the right) of an integer $a$ by

$$\left\lfloor \frac{a}{2^{n-1}}\right\rfloor -\left\lfloor \frac{a}{2^n}\right\rfloor2.$$

To AND the $n$th digits of $a$ and $b$ you just multiply:

$$\left(\left\lfloor \frac{a}{2^{n-1}}\right\rfloor -\left\lfloor \frac{a}{2^n}\right\rfloor2\right)\cdot\left(\left\lfloor \frac{b}{2^{n-1}}\right\rfloor -\left\lfloor \frac{b}{2^n}\right\rfloor2\right).$$

Now just make a binary number out of it: (The number of digits of the larger of $a$ and $b$ is given by $\log_2(a+b)+1$.)

$$a \mbox{ AND } b =\sum_{n=1}^{\log_2 (a+b)+1} \left(\left\lfloor \frac{a}{2^{n-1}}\right\rfloor -\left\lfloor \frac{a}{2^n}\right\rfloor 2\right)\cdot\left(\left\lfloor \frac{b}{2^{n-1}}\right\rfloor -\left\lfloor \frac{b}{2^n}\right\rfloor2\right )2^{n-1}.$$

To do OR, note that if $r$ and $s$ are binary digits, then

$$r \mbox{ OR } s = r+s - rs.$$

So we can OR the digits of $a$ and $b$ and make a binary number of out those:

$$a \mbox{ OR } b =\sum_{n=1}^{\log_2 (a+b)+1} \left(\left(\left\lfloor \frac{a}{2^{n-1}}\right\rfloor -\left\lfloor \frac{a}{2^n}\right\rfloor2\right)+\left(\left\lfloor \frac{b}{2^{n-1}}\right\rfloor -\left\lfloor \frac{b}{2^n}\right\rfloor2\right) -\left(\left\lfloor \frac{a}{2^{n-1}}\right\rfloor -\left\lfloor \frac{a}{2^n}\right\rfloor2\right)\cdot\left(\left\lfloor \frac{b}{2^{n-1}}\right\rfloor -\left\lfloor \frac{b}{2^n}\right\rfloor2\right)\right) 2^{n-1}. $$

Answer 3

(Not sure if this should be a comment, but posting as an answer.)

As B.Goddard has shown, a formula can be produced. But I hope you realize that absolutely no-one uses that to compute the bit-wise AND/OR of two numbers, and certainly not any computer. For the following reasons:

• Computers already store numbers in binary. There's no "convert to binary" step

• Computers are built on circuits that do AND and OR, so they would just do as you indicated with the binary numbers.

• In fact, things like plus, times, and divide are implemented in terms of the logical operations, and are more complicated to carry out than AND and OR.