[FIXED] Fast computation for changing the leftmost different bit

Issue

Given the two number in 8-bit:

x = 0b11110111
y = 0b11001010

What I want to do is to compare x and y and change x only the first different leftmost bit based on y. For example:

z = 0b11010111 (Because the leftmost different bit between x and y is in the third place, therefore, change the third bit in x based on y and other remain the same.)

And my code is:

flag = True
for i in range(8):
    if flag and x[i] != y[i]: # Change only the left-most different bit.
        flag = False
    else:
        y[i] = x[i] # Otherwise,  remain the same.

This could work find.

Buit the problem is if I have many pairs like:

for (x, y) in nums:
    flag = True
    for i in range(8):
        if flag and x[i] != y[i]: # Change only the left-most different bit.
            flag = False
        else:
            y[i] = x[i] # Otherwise,  remain the same.

When nums is large, then this process will be really slow. So how can I improve the process of the problem?

BTW, this is the project of the deep learning task, so it can run on GPU, but I don't know whether it can be paralleled by GPU or not.

Solution

The function you're after:

from math import floor, log2


def my_fun(x, y):
    return x ^ (2 ** floor(log2(x ^ y)))


z = my_fun(0b11110111, 0b11001010)
print(f'{z:b}')

Output:

11010111

The function does the following:

• compute the XOR result of x and y, which will include the most significant bit where they differ as the most significant bit to be 1
• compute the floor of the log2 of that value, and raising 2 to that power, to get a number that only has that bit set to 1
• return the XOR of x and that number, flipping the relevant bit

Answered By - Grismar