782. 与或和

描述

给 n 个非负整数，请你求出最大或和，最小或和，最大与和，最小与和这四个数之和。

注意事项

最大或和为在 n 个数中，任取若干个数（不能不取），进行或运算后最大的数。
最小或和为在 n 个数中，任取若干个数（不能不取），进行或运算后最小的数。
最大与和为在 n 个数中，任取若干个数（不能不取），进行与运算后最大的数。
最小与和为在 n 个数中，任取若干个数（不能不取），进行与运算后最小的数。
1 <= n <= 1000000，0 <= nums[i] <= 2^32 - 1。

样例

给出 n = 3, nums = [1, 2, 3]，返回 7。
解释：
最大或和：3，最小或和：1，最大与和：3，最小与和：0。
答案：3 + 1 + 3 + 0 = 7。

给出 n = 3, nums = [0, 0, 1]，返回 2。
解释：
最大或和：1，最小或和：0，最大与和：1，最小与和：0。
答案：1 + 0 + 1 + 0 = 2。

给出 n = 5, nums = [12313, 156, 4564, 212, 12]，返回25090。
解释：
最大或和：12765，最小或和：12，最大与和：12313，最小与和：0。
答案：12765 + 12 + 12313 = 25090。

给出 n = 3, nums = [111111, 333333, 555555]，返回 1588322。
解释：
最大或和：917047，最小或和：111111，最大与和：555555，最小与和：4609。
答案：917047+ 111111+ 555555+ 4609 = 1588322。

思路

1. 最大与和即为数组中最大数(数组中其他数的最高位的1一定没有最大数的最高位1靠前，一个数与上任何一个比它小的数得到的数一定没有它本身大)
2. 最小或和即为数组中最小数(数组中其他数的最高位的1一定没有最小数的最高位1靠后，一个数或上任何一个比它小的数得到的数一定没有它本身小)
3. 最小与和就是数组中所有数与过之后的数
4. 最大或和就是数组中所有数或过之后的数

代码

public class Solution {
    /**
     * @param n: 
     * @param nums: 
     * @return: return the sum of maximum OR sum, minimum OR sum, maximum AND sum, minimum AND sum.
     */
    public long getSum(int n, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        long maxOr = nums[0];
        long minOr = nums[0];
        long maxAnd = nums[0];
        long minAnd = nums[0];
        long sum = 0;
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > maxAnd) {
                maxAnd = (long)nums[i];
            }
            if (nums[i] < minOr) {
                minOr = (long)nums[i];
            }
            minAnd &= (long)nums[i];
            maxOr |= (long)nums[i];
        }
        
        sum = maxOr + minOr + maxAnd + minAnd;
        return sum;
    }
}