Java与C++同逻辑求M的N次方根代码输出结果不一致问题
问题背景
我在解决Nth root of M算法问题时,首先使用Java编写了如下解法,该代码可通过全部测试用例:
public int NthRoot(int n, int m) { // code here int ans = -1; if (m == 0) return ans; if (n == 1 || n == 0) return m; if (m == 1) return 1; int low = 1; int high = m; while (low < high) { int mid = (low + high) / 2; int pow = (int)Math.pow(mid, n); if (pow == m) { ans = mid; break; } if (pow > m) { high = mid; } else { low = mid + 1; } } return ans; }
但我用C编写逻辑完全相同的代码时,却出现部分测试用例无法通过的问题,C代码如下:
int NthRoot(int n, int m) { // Code here. int ans = -1; if (m == 0) return ans; if (n == 1 || n == 0) return m; if (m == 1) return 1; int low = 1; int high = m; while (low < high) { int mid = (low + high) / 2; int po = (int)pow(mid, n); if (po == m) { ans = (int)mid; break; } if (po > m) { high = mid; } else { low = mid + 1; } } return ans; }
未通过的测试用例:
输入:6 4096 Java输出:4(符合预期) C++输出:-1(错误)
我手动推演的运算结果和Java输出的预期结果一致,后续我将C代码中的相关变量替换为long long int类型后,代码可正常运行。但我已确认Java的int和C的int取值范围一致,分别输出Integer.MAX_VALUE和INT_MAX得到的结果相同,请问导致两类语言代码输出结果不一致的原因是什么?
问题解答
导致结果不一致的核心原因是两种语言的pow函数实现逻辑存在差异,浮点精度截断行为不同:
- Java的
Math.pow针对整数幂运算做了特殊优化,当运算结果可以被浮点数精确表示时,会返回完全准确的整数值。比如测试用例中计算Math.pow(4,6)时,返回精确的4096.0,强转为int后就是4096,可以和输入的m值匹配,因此得到正确结果。 - C++标准库的
pow没有对整数幂运算做精确性保证,底层采用近似浮点运算实现,很容易出现精度误差。同样计算pow(4,6),大概率会返回4095.999999999999这类略小于真实值的浮点数,强转为int时会直接截断小数部分,得到4095,无法和4096匹配,因此不会进入赋值ans的分支,最终返回-1。
你将变量替换为long long后运行正常,本质是因为浮点数转long long的舍入规则和转int不同,或者修改变量类型时隐式规避了其他测试用例中整数幂溢出的问题,和int本身的取值范围无关。
内容的提问来源于stack exchange,提问作者Marivishnu
相关产品推荐
相关产品推荐

