给定 N，return M 满足等式：N + M = 2 * (N XOR M)

Question

问题

Given N, return M that satisfy the equation: N + M = 2 * (N ^ M)

约束条件

1 <= Test Cases = 10^5; 
1 <= N <= 10^18

我在一次招聘挑战中遇到了这个问题。

通过反复试验，我发现了一个模式 - 在 N/3 和 3N 之间存在这样一个 M，并且 N + M是偶数。因此，我将其编码并提交后，我的解决方案仅成功通过了一半的测试用例。这不是什么优化，因为此方法的时间复杂度与蛮力解决方案的时间复杂度相同。

我知道我的解决方案不是最优解。

这是我的解决方案：

def solve(n):
    m = n//3
    end = 3*n
    
    # If both m and n are odd/even, their sum will be even
    if (m&1 == 1 and n & 1 == 1) or (m&1 == 0 and n&1 == 0):
        inc = 2
    else:
        m += 1
        inc = 2

    while m <= end:
        if (n + m) == 2 * (n ^ m):
            return m

        m += inc

有人可以向我提供一些 hints/methods/algorithm 以获得最佳解决方案。谢谢！

Answer 1

m 的最低位已确定（因为 n+m 必须是偶数）。给定最低位，确定下一位，依此类推。

该观察导致这个 O(log n) 解决方案：

def solve(n):
    b = 1
    m = 0
    while n + m != 2 * (n ^ m):
        mask = 2 * b - 1
        if ((n + m) & mask) != ((2 * (n ^ m)) & mask):
            m += b
        b *= 2
    return m

实现这一点的另一种方法是找到 m+n 和 2*(n^m) 不同的最小位，并在 m 中切换该位。这导致了这个非常紧凑的代码（使用新的海象运算符和一些位技巧）：

def solve(n):
    m = 0
    while r := n + m ^ 2 * (n ^ m):
        m |= r & -r
    return m

给定 N，return M 满足等式：N + M = 2 * (N XOR M)

Given N, return M that satisfy the equation: N + M = 2 * (N XOR M)

python

algorithm

bit-manipulation

bitwise-operators

xor