给定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

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

通过反复试验的方法，我发现了一个模式——这样的M存在于N/3和3N之间，并且N+M是偶数。所以我对它进行了编码，提交后，我的解决方案只通过了一半的测试用例。这不是什么优化，因为这种方法的时间复杂性与Brute力解的时间复杂性相同。

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

这是我的解决方案：

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(logn(解决方案：

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

我还没有测试过这个soln，它可能不起作用，但我们开始

已知

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 for even and __1 for odd)相同

假设N是奇数=>___1

因此我们将M作为=>___1

现在让我们计算这些数字中的xor是

xor=> _ _ _ _ 0
AND=> _ _ _ _ 1

我们知道"；"与"；这里应该是left-shifted(2*)因此，我们看到AND的最后一个数字将是xor在最后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));