BAT面试必问:a减b小于0与a小于b什么区别?溢出感知代码?

avatar 2019年11月11日11:11:59BAT面试必问:a减b小于0与a小于b什么区别?溢出感知代码?已关闭评论

BAT面试必问:a-b<0与a<b什么区别?overflow-conscious代码什么玩意?

原创声明

这是本人署名原创文章,未经许可不支持转载。本公众号所有文章均原创。为了容易理解和记忆,文章以图解为主、代码为辅。如果感兴趣,欢迎关注!

:吴潇/Java高级工程师

读过JDK源码的同学,尤其是读过Collection框架的同学,肯定遇到过下面这种代码:

BAT面试必问:a减b小于0与a小于b什么区别?溢出感知代码?

第一次读到这样的代码,你可能跟我一样感到困惑,为什么不直接写成 "newCapacity < minCapacity",而是更麻烦的"newCapacity – minCapacity < 0"呢?

BAT面试必问:a减b小于0与a小于b什么区别?溢出感知代码?

不过,当看到那个注释"overflow-conscious code"之后,你或许明白了一点点,这是为了解决数值溢出问题。

那么"newCapacity < minCapacity"中究竟有什么样的溢出问题?"newCapacity – minCapacity < 0"是怎么解决"newCapacity < minCapacity"中的溢出问题的?究竟是newCapacity和minCapacity中的哪个变量溢出?还是两个变量都溢出?对于这些问题,你都能给出清晰的回答吗?如果不能,欢迎继续阅读!

本文以下面这段代码为例,帮助大家彻底弄明白a<b与a-b<0有何区别的问题。在后面的分析中,我们假设入参a和b都大于0,没有溢出;calc1和calc2是两个计算函数,会返回一个比原来更大的数值,而且可能溢出(例如乘以2、向左移位等)。

BAT面试必问:a减b小于0与a小于b什么区别?溢出感知代码?

首先,上面代码的入参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. 分类讨论方法是一种强大的分析手段,任何让人感到复杂的、没有头绪的问题都可以用它解决)。

BAT面试必问:a减b小于0与a小于b什么区别?溢出感知代码?

分解出4种情况之后,问题就变得简单明了多了,很容易得到a<b与a-b<0的实际结果,是true还是false。另外,期望结果应该是数学上的,不考虑溢出问题。我们经过分析,得到这4种情况下,a<b与a-b<0的实际结果与期望结果的对比,汇总如下:

BAT面试必问:a减b小于0与a小于b什么区别?溢出感知代码?

在上图的分析中,我们没有给出具体数值,只用了模糊的字眼"很大"、"很小"之类的,应该不影响理解。如果你喜欢刨根问底,可以用这段程序分析一下,看看上面的总结对不对。

BAT面试必问:a减b小于0与a小于b什么区别?溢出感知代码?

从上面分析可以看出,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)。

历史上的今天
十一月
11
avatar