这段C++代码和这段Python代码有什么区别？
回答
感谢 @TheDark 发现了溢出的问题。新的 C++ 解决方案也挺搞笑的，实在是太冗余了：
if(2*i > n && 2*i > i)
替换了旧的代码行 if(2*i > n)。
背景
我正在做 HackerRank 上的这个问题，不过这个问题可能和我提问的内容不完全相关。如果你看不到网页，或者不想注册账号，下面有问题的简单描述。
问题
我的 C++ 代码超时了，但我的 Python 代码没有。我最开始怀疑是因为溢出，但我用 sizeof 确认过 unsigned long long 可以达到 2^64 - 1，这是问题的上限。
我几乎是直接把我的 C++ 代码翻译成 Python，想看看是不是我的算法导致了超时，但让我惊讶的是，我的 Python 代码通过了所有测试用例。
C++ 代码：
#include <iostream>
bool pot(unsigned long long n)
{
if (n % 2 == 0) return pot(n/2);
return (n==1); // returns true if n is power of two
}
unsigned long long gpt(unsigned long long n)
{
unsigned long long i = 1;
while(2*i < n) {
i *= 2;
}
return i; // returns greatest power of two less than n
}
int main()
{
unsigned int t;
std::cin >> t;
std::cout << sizeof(unsigned long long) << std::endl;
for(unsigned int i = 0; i < t; i++)
{
unsigned long long n;
unsigned long long count = 1;
std::cin >> n;
while(n > 1) {
if (pot(n)) n /= 2;
else n -= gpt(n);
count++;
}
if (count % 2 == 0) std::cout << "Louise" << std::endl;
else std::cout << "Richard" << std::endl;
}
}
Python 2.7 代码：
def pot(n):
while n % 2 == 0:
n/=2
return n==1
def gpt(n):
i = 1
while 2*i < n:
i *= 2
return i
t = int(raw_input())
for i in range(t):
n = int(raw_input())
count = 1
while n != 1:
if pot(n):
n /= 2
else:
n -= gpt(n)
count += 1
if count % 2 == 0:
print "Louise"
else:
print "Richard"
在我看来，这两种版本看起来一模一样。我还是觉得我可能被某种方式欺骗了，实际上我的 C++ 代码中发生了溢出，导致了超时。
问题描述
路易斯和理查德在玩一个游戏。他们有一个计数器，初始值为 N。路易斯先出手，之后轮流进行。在游戏中，他们执行以下操作。
如果 N 不是 2 的幂，他们就把计数器减去小于 N 的最大 2 的幂。
如果 N 是 2 的幂，他们就把计数器减去 N 的一半。
得到的新值就是新的 N，继续用于后续操作。
游戏在计数器减到 1 时结束，也就是 N == 1，最后一个进行有效操作的人获胜。
给定 N，你的任务是找出游戏的赢家。
输入格式
第一行包含一个整数 T，表示测试用例的数量。接下来的 T 行中，每行包含 N，即计数器的初始值。
约束条件
1 ≤ T ≤ 10
1 ≤ N ≤ 2^64 - 1
输出格式
对于每个测试用例，打印赢家的名字，每个名字占一行。如果路易斯赢了游戏，打印 "Louise"。否则，打印 "Richard"。（引号只是为了说明）
示例输入
1
6
示例输出
Richard
解释
因为 6 不是 2 的幂，路易斯减去小于 6 的最大 2 的幂，即 4，因此计数器减到 2。
因为 2 是 2 的幂，理查德将计数器减去 2 的一半，即 1。因此计数器减到 1。
当我们达到结束条件 N == 1 时，理查德赢得了游戏。
2 个回答
试试这个位运算的小技巧，可能会稍微快一点：
unsigned long largest_power_of_two_not_greater_than(unsigned long x) {
for (unsigned long y; (y = x & (x - 1)); x = y) {}
return x;
}
x&(x-1) 的意思是把 x 中最右边的一个1去掉。所以当 x 变成2的幂时，y 就会变成0，这样循环就结束了。这个2的幂是小于或等于原来的 x 的最大2的幂。循环的次数和 x 中1的个数有关，平均来说，这个方法的循环次数只有你方法的一半。而且，这个方法不会出现溢出的问题。（不过如果原来的 x 是0，它会返回0。这可能是你想要的，也可能不是。）
需要注意的是，如果原来的 x 是2的幂，函数会直接返回这个值。所以这个函数也可以用来判断 x 是否是2的幂（或者是0）。
虽然这个方法挺有趣的，但在实际代码中，你可能更应该找找你编译器里有没有和这个 gcc 内置函数相似的东西（除非你的编译器就是 gcc，那这里就是了）：
- 内置函数：
int __builtin_clz (unsigned int x)返回X中从最高位开始的前导0的个数。如果X是0，结果是未定义的。
（对于 unsigned long 参数，还有 __builtin_clzl；对于 unsigned long long 参数，还有 __builtin_clzll。）
当 n 大于 2 的 63 次方时，你的 gpt 函数最终会让 i 达到 2 的 63 次方，然后再把 2 的 63 次方乘以 2，这样就会出现溢出，结果变成 0。接下来就会陷入一个无限循环，每次都在把 0 乘以 2。