Xor using bitwise operations

Question

Say I have a fn taking two ints A,B

Let binary rep of A be a0,a1,a2....an, and that of B be b0,b1,b2...bn .

I wish to return this ((a0 * b0) ^ (a1 * b1) ^ ..... ^ (an * bn)).

But the challenge is to achieve this without bit conversions i.e. using integers. How can I achieve this?

PS: I know A & B gives me a number. When this number is converted to binary and its elements are xorred amongst each other, I would get my answer. But I do not wish to convert the anded result to binary using bin() for faster computation.

    def find( int A,int B):

      multiply= A & B

      list= bin(multiply)[2:] #(this step I wish to avoid cuz the product can be super large and the binary string is long)

      list = [int(d) for d in list]
    
      innerprod = (reduce(lambda i, j: int(i) ^ int(j), list))

      return innerprod

Answer 1

First bitwise "and" (&) the numbers to get a number whose bits are the bits of the input numbers, multiplied respectively.

You can use Kernighan's algorithm to count the number of bits that are set to 1 (see link for description), in this number.

Then, mod 2 the result, because XOR is just flipping the result every time a bit set to 1 is encountered (so, an even number of 1's XOR'd together is 0, and an odd number will be 1).

Example:

• 7 is '111' and 5 is '101'
• 7 & 5 is '101' (bitwise "and" operation)
• Two bits in '101' are set to 1 (so count_set_bits returns 2)
• 2 modulo 2 is 0.
• (1 * 1) ^ (1 * 0) ^ (1 * 1) is 0

def count_set_bits(n):
    count = 0
    while n:
        n &= (n-1)
        count += 1
    return count

def compute_answer(a, b):
    return count_set_bits(a & b) % 2

print(compute_answer(7, 5))   # 0
print(compute_answer(37, 3))  # 1