2

I was reviewing other posts to find an Arithmetic way for XOR and found this, but cannot apply to natural numbers in python3.

The trivial way:

a = 12
b = 5
a^b ===> 9

Using the other posts formula:

a = 12
b = 5
a + b - a*b*(1 + a + b - (a*b))   ===> 2537

Another option:

a = 12
b = 5
(a-b)**2   ===> 49

Off course, all the previous is working well as the trivial way if a and b are zero or one, like the other posts said, but...

Is there a function for getting XOR with natural numbers in a more Arithmetic way?

UPDATE: Using the code of the response, I built the arithmetic fórmulas in a more mathematical way, just getting more clear the question and the answer. Thank you!

enter image description here

Nand0san
  • 473
  • 4
  • 13
  • As that post indicates, that second one is only for bit numbers (1 or 0) – Max Mar 01 '21 at 21:23
  • And, I think, only to indicate whether they are both non-zero or not, not to give a bit-wise element. Since XOR is only defined for base 2 numbers, I don't think it's actually possible to emulate it using arithmetic expressions (without just breaking them down entirely using divides and mods to break it into a vector of numbers) – Max Mar 01 '21 at 21:27
  • The answer to the question is "no". The AND, OR, and XOR operators are, by definition, operating on bits. There's no decimal/arithmetic equivalent. – Tim Roberts Mar 01 '21 at 21:32
  • XOR is basically binary addition, without carry. So adding the two numbers, then subtracting what would have been carried during addition would work. And carry happens when both numbers have a 1 bit in the same place, which is the same as the AND operation (shifted left by one bit). So `a + b - ((a & b) << 1)` - not sure if that's a good enough answer, as there's still a bitwise operation in there. – jasonharper Mar 01 '21 at 21:35
  • How much "more Arithmetic" do you want it to be? – General Grievance Mar 01 '21 at 21:46
  • You can extract individual bits with integer division/modulo by 2. So you can perform any bitwise operation by doing that in a loop. – interjay Mar 01 '21 at 21:46
  • @Calculuswhiz if possible without bit wise operations – Nand0san Mar 01 '21 at 22:13

1 Answers1

1

First, we have to settle on a definition of "arithmetic." Britannica says it's the "branch of mathematics in which numbers, relations among numbers, and observations on numbers are studied and used to solve problems".

With these ground rules, the following are legal in addition to the usual +-*/:

  • Integer division
  • Modulo (remainder of division)
  • Max and comparison (relations among numbers)

These can be exploited to arithmetically "bit-shift".

The following meets the given criteria:

# By the problem statement, we're dealing with Natural numbers (Z+). No need to check for negatives.

def numBits(x):
    acc = 0
    while x > 0:
        x //= 2
        acc += 1
    return acc

def xor(a, b):
    acc = 0
    pos = 1
    for i in range(numBits(max(a, b))):
        acc += ((a + b) % 2) * pos
        a //= 2
        b //= 2
        pos *= 2

    return acc

# Prints 9
print(xor(12, 5))

Try it online!

"Arithmetic" could include exponentiation and logarithms to save some typing as well, but I kept it down to the more basic operations.

If you're looking for something more single-formula, if you know the bit-width, n, of your numbers beforehand, you can unroll the above loops to a sum of n-terms:

def xor(a, b):
    return ((a + b) % 2) + ((a // 2 + b // 2) % 2) * 2 + ... + ((a // 2 ** n + b // 2 ** n) % 2) * 2 ** n
General Grievance
  • 4,555
  • 31
  • 31
  • 45