algorithm - 这个循环是做什么的？

Question

下面的循环是做什么的？

k = 0
while(b!=0): 
   a = a^b 
   b = (a & b) << 1 
   k = k + 1 

哪里a , b和 k整数。

最初 a = 2⁷⁷⁹ 和 b = 2⁶² 那么 k 的值是多少？循环结束后？

如果你们尝试手动而不是通过编程解决问题，我会很高兴。

编辑:删除标签 c 和 c++。如何手动解决问题？

Answer 1

执行此 block 后:

a = a^b ;
b = (a & b) << 1;

b 将采用在 b 中设置但未在 a 中设置的任何位的整数表示。假设输入数字的形式为 2^x，a 将变为 a + b，并且 b 本身将乘以 2(由于移位)。这意味着当 a 和 b 的 MSB 相同(在本例中为第 780 位)时，循环将终止。由于 b 从第 63 位开始，最终将进行 718 次迭代:780 - 63 + 1(最后一次迭代)= 718。

当您使用 a = 2¹ 和 b = 2⁰ 时，您可以看到这一点:

a = 10
b = 01
k = 0

a = 11
b = 10
k = 1

a = 01 (a + b no longer holds here, but it is irrelevant as this is the termination case)
b = 00
k = 2