给定 N，返回满足方程的 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

有人可以给我一些提示/方法/算法来获得最佳解决方案吗？谢谢！

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

Answer 2

我还没有测试过这个解决方案，它可能不起作用，但我们开始吧

据了解

N+M=(N^M)+(N&M)*2

但是我们有 N+M=2(N^M)

由上面两个方程，我们得到

2(N&M)=(N^M)

这里乘以 2 意味着我们只是左移该值， 所以如果我们得到一个数字，例如

1 0 1 0 =N^M |

0 1 0 1 =N&M

以上解决方案即可满足

我们知道 N 和 M 的最后一位，因为 RHS 始终是偶数，M 的最后一位将与 N 相同（偶数为 __0，奇数为 __1）

我们假设 N 是奇数 => _ _ _ 1

因此我们将 M 设为 => _ _ _ _ 1

现在让我们计算这些数字的异或结果

异或=> _ _ _ _ 0| 并且=> _ _ _ _ 1

我们知道这里的“AND”应该左移(2*) 因此我们看到 AND 的最后一位数字将是最后 1 位置处的异或数字，简单来说：

xor=>      e d c b a (0/1)
AND=>(0/1) e d c b a

我们可以为此编写代码：

下面是java代码：

        int n=sc.nextInt();
        String nBi="0"+Integer.toBinaryString(n);
        StringBuilder mBi=new StringBuilder("");
        int target;
        if(n%2==0){
            mBi.append("0");
            target=0;
        }else{
            mBi.append("1");
            target=1;
        }
        int length=nBi.length();
        for(int i=length-2;i>=0;i--){
            //target for xor is saved in target variable 
            if(target==0){
                //same numbers causes 0 in xor
                mBi.append(nBi.charAt(i));
                target=(int)nBi.charAt(i)&1;
            }else{
                mBi.append(nBi.charAt(i)=='1'?'0':'1');
                target=0;
            }
        }
        int m=Integer.parseInt(mBi.reverse().toString(),2);
        System.out.println(m);  
        System.out.println((n+m)==2*(n^m));