固定宽度整数环境下，是否存在非回文数因reverse_digits函数溢出导致x == reverse_digits(x)？

嗨，针对你的问题，我先梳理下核心逻辑，再结合你已经做的观察和推导来分析：

首先明确问题：我们有这个逐位反转数字的reverse_digits函数，在固定宽度整数（比如32位、64位）环境下会因为溢出得到错误结果。现在要找非回文的非负整数x，恰好因为溢出，使得x == reverse_digits(x)，而且x本身没有前导零。

你已经手动验证了4位整数，还用C暴力扫了无符号32位整数，都没找到这样的x。那64位的情况呢？我们可以顺着你的观察深入分析：

先复盘你的关键观察，再延伸推导 #

观察1：溢出的必要条件

无符号64位整数的最大值是ULONG_MAX = 18446744073709551615（20位数字，首位为1）。要让reverse_digits溢出，x必须满足两个条件：

• 是20位数字：如果x位数少于20位，反转不会溢出，结果完全准确，此时只有回文数才会满足x等于反转值；
• 末位不为0：如果x末位是0，反转后的数会有前导零，但x本身没有前导零，所以x肯定不是回文数，而且反转后的准确值也不可能等于x，这类数直接排除。

另外，20位的数要能放进64位无符号整数，首位只能是1——因为首位≥2的20位数已经超过ULONG_MAX了，所以x的首位x₁=1。

观察2：溢出的触发阈值

把x写成20位数字x₁x₂…x₂₀（x₁=1），reverse_digits的最后一步是计算(x₂₀x₁₉…x₂)*10 + x₁。溢出意味着这个值超过ULONG_MAX，也就是：

(x₂₀x₁₉…x₂) > 1844674407370955161

这里的x₂₀x₁₉…x₂是x去掉首位后的19位数字的反转数，我们叫它y。

观察3：溢出后的等式关系

当z = y*10 +1溢出时，reverse_digits(x)的结果其实是z的低64位。我们需要这个低64位等于原来的x，也就是：

z mod 2⁶⁴ = x

代入z的表达式得到：

(y*10 + 1) mod 2⁶⁴ = x

而y是x去掉首位1后的19位数字的反转，x本身可以表示为：

x = 10¹⁹ + x₂*10¹⁸ + ... + x₂₀

y则是：

y = x₂₀*10¹⁸ + x₁₉*10¹⁷ + ... + x₂

进一步推导：可能性极低的核心原因 #

把上面的等式展开整理后，我们可以得到一个关于数字位x₂~x₂₀的模2⁶⁴等式：

(x₂₀ -1)*(10¹⁹ -1) + x₂*(10 -10¹⁸) ≡0 (mod 2⁶⁴)

这里有几个关键限制：

1. x₂₀是1-9的个位数（因为x末位不为0），x₂是0-9的个位数；
2. 10¹⁹ -1是奇数，和2⁶⁴互质，这意味着等式左边的每一项都受到严格的范围限制；
3. 右边是0模2⁶⁴，而左边是两个个位数相关项的组合，结果必须恰好落在模2⁶⁴等于0的范围内。

举个例子，假设x₂₀=1，那么左边第一项为0，等式简化为x₂*(10 -10¹⁸) ≡0 (mod 2⁶⁴)。但10 -10¹⁸只含有1个2的因子，所以x₂必须是0模2⁶³——但x₂是个位数，只有x₂=0才行。此时y是1开头的19位数（末尾为0），要满足y>1844674407370955161，y的后18位必须大于84467440737095516。但即使满足这个条件，计算溢出后的低64位，也很难恰好等于原x（比如我们构造一个符合条件的x，计算后发现溢出结果和x相差很大）。

总结 #

从你的暴力验证和64位的推导来看，目前没有找到这样的x，而且存在以下几个理由说明这类x极有可能不存在：

• 满足溢出条件的x范围极小，只有首位为1、末位非0的20位数；
• 要同时满足溢出后低64位等于原数，数字位之间需要满足非常严格的模等式，而个位数的限制进一步压缩了可能性；
• 即使满足模等式，实际计算溢出后的结果也很难恰好等于原数。

如果要彻底验证64位的情况，暴力遍历所有20位数不现实，但可以基于上述推导的条件缩小范围（比如只遍历x₂₀=1_9、x₂=09的组合，再推导其他位的可能），编写针对性的程序进行验证。

备注：内容来源于stack exchange，提问作者Alex R