Java整型溢出的一点新收获

发表于

5844、数组元素的最小非零乘积

给你一个正整数 p 。你有一个下标从 1 开始的数组 nums ，这个数组包含范围 [1, 2p - 1] 内所有整数的二进制形式（两端都 包含）。你可以进行以下操作任意次：从 nums 中选择两个元素 x 和 y  。
选择 x 中的一位与 y 对应位置的位交换。对应位置指的是两个整数 相同位置 的二进制位。比方说，如果 x = 1101 且 y = 0011 ，交换右边数起第 2 位后，我们得到 x = 1111 和 y = 0001 。请你算出进行以上操作 任意次 以后，nums 能得到的 最小非零 乘积。将乘积对 109 + 7 取余 后返回。注意：答案应为取余 之前 的最小值。

其实很快就能找到规律，但是这题问题就在于，求解过程中数字溢出，需要在每一处可能溢出的地方进行取余操作，同时配合记忆化递归进行快速幂求解。

下面是最终的代码，可以看到在很多处都进行了取余操作，因为求2^60级别的乘法中稍稍不注意就会Long型溢出了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int minNonZeroProduct(int p) {
        // int的最大值是 2^31 - 1
        if (p == 1) return 1;
        long r = (long)Math.pow(2, p) - 1;
        
        long res = r % mod;    //取余
        res *= getPow(r - 1, r / 2);
        res %= mod;    //取余
        return (int)res;
    }
    
    long mod = 1000000007;
    HashMap<Long, Long> map = new HashMap<>();
    public long getPow(long num, long multi) {
        if (multi == 1) return num;
        if (map.containsKey(multi)) return map.get(multi);
        
        long res = getPow(num, multi / 2) % mod;   //取余
        res *= getPow(num, multi / 2) % mod;    //取余
        res %= mod;    //取余

        if (multi % 2 == 1) {
            res *= num % mod;     //取余
        }

        res %= mod;    //取余
        // System.out.println(res);
        map.put(multi, res);
        return res;
    }
}

还有一个问题在于：

long r = (int)Math.pow(2, p) - 1; 这句当p等于31时，按理说2 ^ 31转化为int时会溢出，结果应该是 -2147483648 - 1 = 2147483647，但是结果却是2147483646；当我在本地IDE进行(int)Math.pow(2, 31) 这个运算时，得到的结果也是2147483647，这就有点匪夷所思了。

初步排除了无符号的原因，因为如果是无符号，那最大值应该是2 ^ 32 - 1，那么Math.pow(2, 31) 应该得到的是2147483648。

想想这可能是JDK内部实现时进行的什么改变，下面是Java官方文档对于类型转换的解释：

Narrowing Primitive Conversion

22 specific conversions on primitive types are called the narrowing primitive conversions:

  • short to byte or char
  • char to byte or short
  • int to byte, short, or char
  • long to byte, short, char, or int
  • float to byte, short, char, int, or long
  • double to byte, short, char, int, long, or float

A narrowing primitive conversion may lose information about the overall magnitude of a numeric value and may also lose precision and range.

A narrowing primitive conversion from double to float is governed by the IEEE 754 rounding rules (§4.2.4). This conversion can lose precision, but also lose range, resulting in a float zero from a nonzero double and a float infinity from a finite double. A double NaN is converted to a float NaN and a double infinity is converted to the same-signed float infinity.

A narrowing conversion of a signed integer to an integral type T simply discards all but the n lowest order bits, where n is the number of bits used to represent type T. In addition to a possible loss of information about the magnitude of the numeric value, this may cause the sign of the resulting value to differ from the sign of the input value.

A narrowing conversion of a char to an integral type T likewise simply discards all but the n lowest order bits, where n is the number of bits used to represent type T. In addition to a possible loss of information about the magnitude of the numeric value, this may cause the resulting value to be a negative number, even though chars represent 16-bit unsigned integer values.

A narrowing conversion of a floating-point number to an integral type T takes two steps:

  1. In the first step, the floating-point number is converted either to a long, if T is long, or to an int, if T is byte, short, char, or int, as follows:
    1. If the floating-point number is NaN (§4.2.3), the result of the first step of the conversion is an int or long 0.
    2. Otherwise, if the floating-point number is not an infinity, the floating-point value is rounded to an integer value V, rounding toward zero using IEEE 754 round-toward-zero mode (§4.2.3). Then there are two cases:
      1. If T is long, and this integer value can be represented as a long, then the result of the first step is the long value V.
      2. Otherwise, if this integer value can be represented as an int, then the result of the first step is the int value V.
    3. Otherwise, one of the following two cases must be true:
      1. The value must be too small (a negative value of large magnitude or negative infinity), and the result of the first step is the smallest representable value of type int or long.
      2. The value must be too large (a positive value of large magnitude or positive infinity), and the result of the first step is the largest representable value of type int or long.
  2. In the second step:
    ◦ If T is int or long, the result of the conversion is the result of the first step.
    ◦ If T is byte, char, or short, the result of the conversion is the result of a narrowing conversion to type T (§5.1.3) of the result of the first step.

加粗的地方就是上面这种情况，从double转为int型中的第3中情况，当浮点数的值是转为后的数据类型的infinity时，如果超过负极值，就转为MIN_VALUE，如果超过正极值，就转为MAX_VALUE;

所以并不是所有的情况都会溢出。