组数制进二

/*
When x is larger, sum() is also larger.
=> Find the smallest x in range [0, 0b1...1 where #1 == 0bmax(ai)'s 1s]
=> such that the sum() is at max

Binary Search
search range: x in [1, 0b1...1 where #1s == #0bmax(ai)'s digits]
    given that 0 <= ai < 2^30: #0bmax(ai)'s digits <= 30
search for what: First Occurrence of x such that sum() is at max
    assumption: as x goes up, sum() continues going up to a point and will no longer increase
    => Last Occurrence of x such that sum()_when_x > sum()_when_x-1

Complexity:
TC: O(occurrence BS) * O(determine sum() for each x) = O(30) * O(n) ~ O(n)
*/

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int numCases = in.nextInt();
        for (int i = 0; i < numCases; i++) {
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int j = 0; j < n; j++) {
                arr[j] = in.nextInt();
            }

            Result result = smallestXLargestSum(arr);
            System.out.println(result.sum + " " + result.x);
        }
    }

    // Helpers
    /* Given an arr[], return the smallest x where 0bx has #digits <= 0blargest ai's #digits
     * such that sum(ai) is the largest.
     */
    private static Result smallestXLargestSum(int[] arr) {
        int largestNumDigits = getLargestNumDigits(arr);
        int largestX = 1;
        for (int i = 1; i < largestNumDigits; i++) { // shifting & filling with 1
            largestX <<= 1;
            largestX |= 1;
        }
        // System.out.println("largestX = " + largestX);
        // At this point, largestX = 0b1...1 (#1s == largestNumDigits)

        // initialize Occurrence BS
        int left = 1;
        int right = largestX;
        long prevSum = getSumWithX(0, arr); // sum() when x = 1
        int midX = 0; // represent x

        while (left < right - 1) {
            midX = left + (right - left) / 2;
            long currSum = getSumWithX(midX, arr);
            if (currSum > prevSum) { // search to the right of mid (inclusive)
                left = midX;
                prevSum = currSum;
            } else { // prevSum >= currSum
                right = midX - 1;
            }
        }

        // post processing
        long sumWithRightX = getSumWithX(right, arr);
        if (right - 1 >= 0 && sumWithRightX > getSumWithX(right - 1, arr)) {
            return new Result(sumWithRightX, right);
        }
        long sumWithLeftX = getSumWithX(left, arr);
        if (left - 1 >= 0 && sumWithLeftX > getSumWithX(left - 1, arr)) {
            return new Result(sumWithLeftX, right);
        }
        else return new Result(getSumWithX(0, arr), 0);
    }

    // Given an x, return the sum() by applying the formulas.
    private static long getSumWithX(int x, int[] arr) {
        long sum = 0;
        for (int num: arr) {
            sum += num | x;
            x = num & x;
        }

        // System.out.println("When x = " + x + ", sum() = " + sum);
        return sum;
    }

    // return the #digits of binary form of the largest ai. Assert return number is in range 1 ~ 30
    private static int getLargestNumDigits(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
        }

        int numDigits = 0;
        if (max == 0) return 1;

        while (max > 0) {
            numDigits++;
            max >>= 1;
        }
        // System.out.println("for current arr with length = " + arr.length + ", largestNumDigits = " + numDigits);
        return numDigits;
    }
}

class Result {
    long sum;
    int x;

    public Result(long sum, int x) {
        this.sum = sum;
        this.x = x;
    }
}