Can one emulate bitwise arithmetic "and" or "or" using only non-bitwise operations?

Question

Imagine we are tasked with using an idealized scientific calculator which has the following properties:

• no direct support for bitwise operations, or for base conversions (eg cannot simply "convert to" base 2 or base 16 etc)

• Full support for four basic arithmetic functions (+, -, *, /)

• Full support for trig functions, logarithm, exponentiation, roots. For simplicity sake we can assume the trig functions just use Radians.

• Supports parenthesis and standard PEMDAS order of operations

• Even has full support for the following piecewise functions

-- ceil (towards positive infinity)

-- floor (towards negative infinity)

-- truncate (drop fractional component, eg round towards zero)

-- absolute value

-- sign (negative numbers yield -1, positive numbers yield +1, exact zero yields zero)

-- modulo ( same as b*(a/b-floor(a/b)) )

• It can handle N significant digits of precision, where how large N is isn't terribly relevant. I include this proviso just because math can get weird when we don't define some kind of finite bounds on precision.

• Calculator can also store and recall individual numbers on the readout into a handful of registers, clear each or all of the registers, and clear the display.

Our task

is to work out a method to calculate either the bitwise "and" or the bitwise "or" for any two arbitrary non-negative integers using only this calculator.

For example

bitwise "not" is easily enough done by the following expression:

2^ceil(log(input+1)/log(2)) - input - 1

That reverses every binary bit of the input value up to and not beyond its most significant bit.

One can do the same for a fixed constant bit width:

2^bitWidth - input - 1

as long as input < 2^bitWidth

Another example

bitwise shift towards more significant bits (aka bitshift left, assuming both most significant bit first and left to write notation) can be easily handled via input*2

Constraint

• I would like the solution to involve a fixed number of steps that does not change with the size of the inputs O(1). In particular having to extract and handle individual binary digits in a loop is a bridge too far.

Relaxed constraints

• Our algorithm is free to render undefined nonsense for invalid input

• to be valid, input must be non-negative integers

• We will simply assume that the calculator we use has enough precision to handle whatever math we try on whatever sized inputs we try without succumbing to floating point rounding errors

Motivation

I know that all classical mathematical operations can be computed using only bitwise operations. I am endeavoring to determine if the opposite can be shown to work as well. And given that I can perform "not" I understand that either being able to accomplish "and" ⋀ or being able to accomplish "or" ⋁ should crack open the way to being able to accomplish every permutation of bitwise operation thereafter. :)

I have tried variations on simple addition to achieve an "or" output, but being able to detect and/or correct for potential carries still has me stymied on that approach. For example a+b == a⋁b iff (a⋀b==0). Were I able to either detect when (a⋀b!=0), and/or reverse the carries (subtract a⋀b*2 from the result) that could get me a step closer.

Answer 1

hmm this reminds me of a question posted here maybe few months ago about doing logical functions using arithmetic ones but too lazy to look for it...

You can extract binary digits of b like this

b0 = x%1
b1 = (x/2)%1
b2 = (x/4)%1
...

and reconstruct back:

b = b0 + 2*b1 + 4*b2 + ...

now you can compute c = a AND b like this:

c0 = a0*b0
c1 = a1*b1
c2 = a2*b2
...
c = c0 + 2*c1 + 4*c2 + ...

now you have AND and NOT you already implemented so you can use De Morgan's laws to implement any logical function using NAND...

NOT(A OR  B) = NOT(A) AND NOT(B)
NOT(A AND B) = NOT(A) OR  NOT(B)

or you can use Karnough maps to implement any logical function using just NAND ...

Answer 2

A simple, reasonably efficient, and portable solution would be to use a look-up table. If the modulus operator is not allowed, it can be replaced easily as A % B is equivalent to A - B*(A/B) in integer arithmetic, A - B*floor(A/B) otherwise. Any bitwise logical operator on two integers can be calculated this way with an appropriate look-up table. Here is an example of how logical OR can be emulated on 32 bit integers.

uint32_t logicalOR(uint32_t A, uint32_t B) {
  uint32_t res, Anibble, Bnibble;
  uint8_t lut[16][16] = {....};
  res = 0;
  Anibble = A / 0x10000000;
  Bnibble = B / 0x10000000;
  res = lut[Anibble][Bnibble];
  Anibble = (A / 0x1000000) % 16;
  Bnibble = (B / 0x1000000) % 16;
  res = (res * 16) + lut[Anibble][Bnibble];
  Anibble = (A / 0x100000) % 16;
  Bnibble = (B / 0x100000) % 16;
  res = (res * 16) + lut[Anibble][Bnibble];
  Anibble = (A / 0x10000) % 16;
  Bnibble = (B / 0x10000) % 16;
  res = (res * 16) + lut[Anibble][Bnibble];
  Anibble = (A / 0x1000) % 16;
  Bnibble = (B / 0x1000) % 16;
  res = (res * 16) + lut[Anibble][Bnibble];
  Anibble = (A / 0x100) % 16;
  Bnibble = (B / 0x100) % 16;
  res = (res * 16) + lut[Anibble][Bnibble];
  Anibble = (A / 0x10) % 16;
  Bnibble = (B / 0x10) % 16;
  res = (res * 16) + lut[Anibble][Bnibble];
  Anibble = A % 16;
  Bnibble = A % 16;
  res = (res * 16) + lut[Anibble][Bnibble];
  return res;
}