CODEWITHSUNDEEP
pythonxorarithmetic-expressions
Nand0san
Nand0san

Reputation: 511

XOR arithmetically defined with operations for natural numbers (or integers)

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

Upvotes: 2

Views: 388

Answers (1)

General Grievance
General Grievance

Reputation: 5023

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

Upvotes: 1

Related Questions