谷歌代码堵塞2020，第1B轮刚刚结束，我对"Expogo"任务感到非常困惑：
您需要从
(0, 0)开始到达(X, Y)。你可以向北/向东/向南/向西移动。在时间i，步长为2**i(从i=0开始，每移动一步增加一步(。找到通向(X，Y(的最短序列，或者如果不可能到达那里。
看看几个解决方案(例如Linguo、ctunoku、roflmoqkz、jaems、chaotic_iak(，我经常看到这种解决方案(取自chaotic_aik，应用黑色(：
def solve(x, y):
if x % 2 == y % 2:
return "IMPOSSIBLE"
s = ""
while x != 0 or y != 0:
# Handling the easy cases:
if abs(x) + abs(y) == 1:
if x == 1:
return s + "E"
if x == -1:
return s + "W"
if y == 1:
return s + "N"
if y == -1:
return s + "S"
# This is what I don't get:
if x % 2 == 1:
y //= 2
if (y % 2 == 1 and x % 4 == 1) or (y % 2 == 0 and x % 4 == 3):
x = (x - 1) // 2
s += "E"
else:
x = (x + 1) // 2
s += "W"
else:
x //= 2
if (x % 2 == 1 and y % 4 == 1) or (x % 2 == 0 and y % 4 == 3):
y = (y - 1) // 2
s += "N"
else:
y = (y + 1) // 2
s += "S"
这个问题似乎有一个关键的见解，但我不明白。首先，为什么相同的奇偶性意味着这是不可能的？我可以看出(1，1(是不可能的，因为你可以很容易地得到第一个1，然后你只能得到2。但如何证明这是不可能的呢？
我的主要问题是：为什么作者除以2步骤的顺序很重要。步骤的长度为2*i，其中i是第i个步骤(从0开始(。为什么要添加+1？
我所理解的
让我们只关注X，并假设它是正的。然后有一条路要走，就是得到二进制表示。对于每个具有1的位置，都需要转到E。在其他情况下，需要做其他事情。
代替在步骤i中取一个E，还可以在i+1中取E，在i中取W。这样，一个人可以有无限多个表示：
5 = 101
= E0E : 4 + 1
= EEW : 4 + 2 - 1
= EW0E : 8 - 4 + 1
= EWW0E : 16 - 8 - 4 + 1
= EWWW0E : 32 - 16 - 8 - 4 + 1
= ...
我们无法获得相同的奇偶校验，因为只有第一次移动是奇数的，所以它要么应用于X轴，要么应用于Y轴，而不是同时应用于两者。
在这种情况下，除以2只是一种方便的方法，可以从最低到最高检查每个位。由于我们必须将每个位用作减法(南和西(或加法(北和东(，因此在两个坐标之间可能会出现两个问题，这两个问题都会通过这两个语句的失败来检测：
(x % 2 == 0 and y % 4 == 3)
(x % 2 == 1 and y % 4 == 1)
首先，我们可以在两个坐标的下一个位置都有一个未设置的位，这意味着x有一个零，而y % 4 = 1意味着y的下一位也是零。在这种情况下，我们在y上加1，这实际上是在加2^p，其中p是指针的当前位置。这将y坐标的当前设置位向左移动，并在当前位置创建零(减法(。
示例：(4，1(
x: 100
y: 1
^--- problem
solution: add 2^0 to y, creating a subtraction
110
south, north, east
第二个问题是，x和y都可能在下一个位置设置了一个位。这是当x有一个设置位和y % 4 == 3时，意味着y的当前位和下一个位都被设置。在这种情况下，将2^p(当前比特(添加到y将翻转y中的这两个比特(以及所有与左边相邻的比特(，因此使用第一个比特作为减法，并释放第二个比特供x使用。
示例：(6,3(
x: 110
y: 11
^--- problem
solution: add 2^0 to y, creating a subtraction
x: 110
y: 100
^--- problem
solution: add 2^1 to x, creating a subtraction
x: 1000
y: 100
south, west, north, east
x: - 2 + 8 = 6
y: - 1 + 4 = 3
根据一些示例的代码结果，我想出了这个例程。它表明，将x + y + s表示为二次幂的最小二进制数N，其中s等于NOT(N)(即减去s，或"西"one_answers"南"运动，可以生成x + y(，可以通过添加x + y + (NOT(x + y) >> 1)来生成。
function f(x, y){
let xy = x + y
console.log((xy).toString(2))
let p = 1
let s = 0
xy >>= 1
while (xy){
if (!(xy & 1))
s |= p
xy >>= 1
p <<= 1
}
console.log(s.toString(2))
console.log((x + y + s).toString(2))
console.log('')
}
var cs = [
[8, 9],
[2, 3],
[10, 5]
]
for (let [x,y] of cs)
f(x,y)