第1章 整数

1.1 整数的基础知识

整数是一种基本的数据类型。编程语言可能会提供占据不同内存空间的整数类型，每种类型能表示的整数的范围也不相同。例如，Java中有4种不同的整数类型，分别为8位的byte（-2⁷～2⁷-1）、16位的short（-2¹⁵～2¹⁵-1）、32位的int（-2³¹～2³¹-1）和64位的long（-2⁶³～2⁶³-1）。

Java中的整数类型都是有符号整数，即如果整数的二进制表示的最高位为0则表示其为正数，如果整数的二进制表示的最高位为1则表示其为负数。有些语言（如C/C++）支持无符号整数。无符号整数无论二进制表示的最高位是0还是1，都表示其为一个正数。无符号的32位整数的范围是0～2³²-1。

通常，编程语言中的整数运算都遵循四则运算规则，可以使用任意嵌套的小括号。需要注意的是，由于整数的范围限制，如果计算结果超出了范围就会产生溢出。产生溢出时运行不会出错，但结果可能会出乎意料。如果除数为0，那么整数的除法在运行时将报错。

面试题1：整数除法

分析：这个题目限制我们不能使用乘号和除号进行运算。一个直观的解法是基于减法实现除法。例如，为了求得15/2的商，可以不断地从15里减去2，当减去7个2之后余数是1，此时不能再减去更多的2，因此15/2的商是7。我们可以用一个循环实现这个过程。

但这个直观的解法存在一个问题。当被除数很大但除数很小时，减法操作执行的次数会很多。例如，求（2³¹-1）/1，减1的操作将执行2³²-1次，需要很长的时间。如果被除数是n，那么这种解法的时间复杂度为O（n）。我们需要对这种解法进行优化。

可以将上述解法稍做调整。当被除数大于除数时，继续比较判断被除数是否大于除数的2倍，如果是，则继续判断被除数是否大于除数的4倍、8倍等。如果被除数最多大于除数的2^k倍，那么将被除数减去除数的2^k倍，然后将剩余的被除数重复前面的步骤。由于每次将除数翻倍，因此优化后的时间复杂度是O（logn）。

下面以15/2为例讨论计算的过程。15大于2，也大于2的2倍（即4），还大于2的4倍（即8），但小于2的8倍（即16）。于是先将15减去8，还剩余7。由于减去的是除数的4倍，减去这部分对应的商是4。接下来对剩余的7和除数2进行比较，7大于2，大于2的2倍（即4），但小于2的4倍（即8），于是将7减去4，还剩余3。这一次减去的是除数2的2倍，对应的商是2。然后对剩余的3和除数2进行比较，3大于2，但小于2的2倍（即4），于是将3减去2，还剩余1。这一次减去的是除数的1倍，对应的商是1。最后剩余的数字是1，比除数小，不能再减去除数了。于是15/2的商是4+2+1，即7。

上述讨论假设被除数和除数都是正整数。如果有负数则可以将它们先转换成正数，计算正数的除法之后再根据需要调整商的正负号。例如，如果计算-15/2，则可以先计算15/2，得到的商是7。由于被除数和除数中有一个负数，因此商应该是负数，于是商应该是-7。

将负数转换成正数存在一个小问题。对于32位的整数而言，最小的整数是-2³¹，最大的整数是2³¹-1。因此，如果将-2³¹转换为正数则会导致溢出。由于将任意正数转换为负数都不会溢出，因此可以先将正数都转换成负数，用前面优化之后的减法计算两个负数的除法，然后根据需要调整商的正负号。

最后讨论可能的溢出。由于是整数的除法并且除数不等于0，因此商的绝对值一定小于或等于被除数的绝对值。因此，int型整数的除法只有一种情况会导致溢出，即（-2³¹）/（-1）。这是因为最大的正数为2³¹-1，2³¹超出了正数的范围。

在全面地分析了使用减法实现除法的细节之后，我们可以开始编写代码。参考代码如下所示：

上述代码中的0x80000000为最小的int型整数，即-2³¹，0xc0000000是它的一半，即-2³⁰。

函数divideCore使用减法实现两个负数的除法。当除数和被除数中有一个负数时，商为负数。因此，在使用函数divideCore计算商之后，需要再根据除数和被除数的负数的个数调整商的正负号。