Java实现数组子数组按位或之和，大测试用例失败求排查

给定大小为N的整数数组A，子数组的值定义为其所有元素的按位或（BITWISE OR），需返回所有子数组的值之和对10^9 + 7取模的结果。

public class Solution {
    public int solve(ArrayList<Integer> A) {
        long M = 1000000007;

        int N = A.size();
        
        long totalSubarrays = (N*(N+1))/2;
        long totalORSum = 0; //sum of bitwise OR of all subarrays
        
        //step1: traverse through each bit of element of array
        for(int i = 0; i < 32; i++) {
            long subArrayUnsetBit = 0;
            long zeroCount = 0;
            for(int j = 0; j < N; j++) {
                //2.check if bit is unset(0).count the number of unset bits.
                //Calculate the number of sub arrays with unset ith bit position

                //for each element, check if bit at "position" is unset
                //if it's unset, add to the total
                //since we are looking for number of subarrays, if there are continuous unset bit position, the number of subarrays will depend on it as well. 
                if ((1 & (A.get(j) >> i)) != 1) {
                    zeroCount++;
                } else {
                    subArrayUnsetBit = subArrayUnsetBit + (zeroCount * (zeroCount + 1)) / 2;
                    zeroCount = 0;//reset
                }

            }
            //get the number of subarrays which have ith bit as unset
            subArrayUnsetBit = subArrayUnsetBit + (zeroCount*(zeroCount+1))/2;
            //number of sub arrays which have ith bit set
            long subArraySetBit = totalSubarrays - subArrayUnsetBit;
            //if ith bit is set, its value would be: 2^i == (1<<i)
            long powerValue = (1<<i);
            //contribution to total sum by all subarrays which has set bit at ith position
            long contribution = (subArraySetBit * powerValue);
            totalORSum = (totalORSum + contribution);

        }
        return (int)(totalORSum % M);
        
    }
}

上述代码在小数组（如[1,2,3,4,5]，预期结果71）中运行正常，但在大测试用例中执行失败，请求帮忙排查问题原因。

代码在大测试用例中失败的核心原因是整数溢出和模运算不规范，具体问题及修复如下：

1. 左移操作的int溢出 #

当i=31时，1 << i中的1是int类型（32位有符号），左移31位会触发符号位变化，得到负数-2147483648，而非预期的2^31，直接导致后续贡献值计算错误。

修复：将1改为1L，以long类型执行左移操作：

long powerValue = 1L << i;

2. 子数组总数计算的int溢出 #

当N较大时（如N=46341），N*(N+1)的结果会超过int类型的最大值（2147483647），先以int计算会溢出，再转long得到错误的totalSubarrays值。

修复：将N转为long后再计算：

long totalSubarrays = ((long)N * (N + 1)) / 2;

3. 大数乘法的溢出与模运算缺失 #

当N达到1e5级别时，subArraySetBit * powerValue的结果会超过long类型的最大值（9223372036854775807），导致溢出；同时未在计算过程中分步取模，最终totalORSum也会溢出。

修复：利用模运算性质(a*b) mod m = [(a mod m)*(b mod m)] mod m，分步对贡献值取模，并在累加后立即对totalORSum取模：

long contribution = ((subArraySetBit % M) * (powerValue % M)) % M;
totalORSum = (totalORSum + contribution) % M;

修复后的完整代码 #

public class Solution {
    public int solve(ArrayList<Integer> A) {
        final long M = 1000000007;

        int N = A.size();
        long totalSubarrays = ((long)N * (N + 1)) / 2;
        long totalORSum = 0;

        for(int i = 0; i < 32; i++) {
            long subArrayUnsetBit = 0;
            long zeroCount = 0;
            for(int j = 0; j < N; j++) {
                if (((A.get(j) >> i) & 1) != 1) {
                    zeroCount++;
                } else {
                    subArrayUnsetBit += (zeroCount * (zeroCount + 1)) / 2;
                    zeroCount = 0;
                }
            }
            subArrayUnsetBit += (zeroCount * (zeroCount + 1)) / 2;
            long subArraySetBit = totalSubarrays - subArrayUnsetBit;
            long powerValue = 1L << i;
            long contribution = ((subArraySetBit % M) * (powerValue % M)) % M;
            totalORSum = (totalORSum + contribution) % M;
        }
        return (int)(totalORSum % M);
    }
}

内容的提问来源于stack exchange，提问作者HK123