|
|
BAT面试必问：a-b<0与a<b什么区别？overflow-conscious代码什么玩意？
原创声明
这是本人署名原创文章，未经许可不支持转载。本公众号所有文章均原创。为了容易理解和记忆，文章以图解为主、代码为辅。如果感兴趣，欢迎关注！
文：吴潇/Java高级工程师
读过JDK源码的同学，尤其是读过Collection框架的同学，肯定遇到过下面这种代码：
第一次读到这样的代码，你可能跟我一样感到困惑，为什么不直接写成 "newCapacity < minCapacity"，而是更麻烦的"newCapacity – minCapacity < 0"呢？
不过，当看到那个注释"overflow-conscious code"之后，你或许明白了一点点，这是为了解决数值溢出问题。
那么"newCapacity < minCapacity"中究竟有什么样的溢出问题？"newCapacity – minCapacity < 0"是怎么解决"newCapacity < minCapacity"中的溢出问题的？究竟是newCapacity和minCapacity中的哪个变量溢出？还是两个变量都溢出？对于这些问题，你都能给出清晰的回答吗？如果不能，欢迎继续阅读！
本文以下面这段代码为例，帮助大家彻底弄明白a<b与a-b<0有何区别的问题。在后面的分析中，我们假设入参a和b都大于0，没有溢出；calc1和calc2是两个计算函数，会返回一个比原来更大的数值，而且可能溢出（例如乘以2、向左移位等）。
首先，上面代码的入参a和b一开始都大于0。a经过calc1()之后，一定变大而且可能溢出；b经过calc2()也必然比原来的b大，也可能溢出。想通过"a-b<0"或"a<b"返回两者中较小的一个。
显然，a和b不溢出时，a-b<0与a<b等价，没啥好分析的。是a溢出或b溢出导致了a-b<0与a<b之间的不同。所以我们的分析思路应该是，讨论分别在"a，b都不溢出"、"a溢出，b不溢出"、"a不溢出，b溢出"及"a，b都溢出"这4种情况下，"a<b"与"a-b<0"的结果如何，这些结果分别与预期结果是否相同，这样就能把问题分析清楚了。所以，我们用分类讨论的方法来分析问题，如下图（ps. 分类讨论方法是一种强大的分析手段，任何让人感到复杂的、没有头绪的问题都可以用它解决）。
分解出4种情况之后，问题就变得简单明了多了，很容易得到a<b与a-b<0的实际结果，是true还是false。另外，期望结果应该是数学上的，不考虑溢出问题。我们经过分析，得到这4种情况下，a<b与a-b<0的实际结果与期望结果的对比，汇总如下：
在上图的分析中，我们没有给出具体数值，只用了模糊的字眼"很大"、"很小"之类的，应该不影响理解。如果你喜欢刨根问底，可以用这段程序分析一下，看看上面的总结对不对。
从上面分析可以看出，a-b<0这样的写法不是万能的，并不能解决全部溢出问题，它在某些溢出情况下的依然错误。而JDK之所以采用这种写法，是因为a和b的数值比较接近，而且都是大数，在这个时候，a和b中有一个变量先溢出，另一个数往往很大了（快要溢出），用a-b<0的写法刚好得到正确结果。JDK采用的这种a-b<0写法，一般出现在各种空间分配方法中，例如ensureCapacity。而分配空间的时候，新分配的空间大小数值虽然比上一次的大，但是也比老的值差不了多少，巧妙的用上了上述绿色区域，实现了在数值溢出的情况下，依然正确的特性，非常神奇。
你弄懂了吗？欢迎留言
以上分析希望对您的工作和面试都有帮助。如果对互联网编程技术、Java、Spring、Android、C/C++、Linux、个性化推荐、Community Detection、Machine Learning、Deep Learning、Data Mining、Gnuplot、LaTeX等技术感兴趣的话，欢迎关注本公众号(不限于Java)。
|
|
发表于 2021-2-17 21:21:43
