题解 | #组数制进二#

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<long long> a(n);
    long long and_all = -1; // 记录所有元素的按位与结果, -1的二进制全是1, 适合做初始值
    long long max_val = 0;  // 记录数组中的最大值

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (and_all == -1) { // 处理第一个元素
            and_all = a[i];
        } else {
            and_all &= a[i];
        }
        max_val = max(max_val, a[i]);
    }

    if (n == 1) { // 特殊情况：数组只有一个元素
        cout << a[0] << " " << 0 << "\n";
        return;
    }

    long long k = 0;
    int bits;
    if (max_val == 0) { // 特殊处理最大值为0的情况
        bits = 1;
    } else {
        bits = floor(log2(max_val)) + 1; // 计算最大值的二进制位数
    }
    long long mask = (1LL << bits) - 1;  // 创建一个位数限制的掩码
    k = (~and_all) & mask;               // 计算最优k值

    long long max_sum = 0;
    for (int j = 0; j < bits; ++j) { // 遍历每一位计算贡献
        long long c_j = 0;
        for (long long x : a) {
            if ((x >> j) & 1) {
                c_j++;
            }
        }
        long long k_j = (k >> j) & 1;
        long long c_j_final = min((long long)n, c_j + k_j);
        max_sum += c_j_final * (1LL << j);
    }
    
    cout << max_sum << " " << k << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        long[] a = new long[n];
        long and_all = -1; // 记录所有元素的按位与结果, -1的二进制全是1, 适合做初始值
        long max_val = 0;  // 记录数组中的最大值

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            if (and_all == -1) { // 处理第一个元素
                and_all = a[i];
            } else {
                and_all &= a[i];
            }
            max_val = Math.max(max_val, a[i]);
        }

        if (n == 1) { // 特殊情况：数组只有一个元素
            System.out.println(a[0] + " " + 0);
            return;
        }

        long k = 0;
        int bits;
        if (max_val == 0) { // 特殊处理最大值为0的情况
            bits = 1;
        } else {
            // 计算最大值的二进制位数
            bits = 64 - Long.numberOfLeadingZeros(max_val);
        }
        // 创建一个位数限制的掩码
        long mask = (1L << bits) - 1;
        // 计算最优k值
        k = (~and_all) & mask;
        
        long maxSum = 0;
        for (int j = 0; j < bits; j++) { // 遍历每一位计算贡献
            long c_j = 0;
            for (long x : a) {
                if (((x >> j) & 1) == 1) {
                    c_j++;
                }
            }
            long k_j = (k >> j) & 1;
            long c_j_final = Math.min(n, c_j + k_j);
            maxSum += c_j_final * (1L << j);
        }
        
        System.out.println(maxSum + " " + k);
    }
}

import math

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    if n == 1:  # 特殊情况：数组只有一个元素
        print(a[0], 0)
        return

    and_all = a[0]  # 记录所有元素的按位与结果
    max_val = 0     # 记录数组中的最大值
    for x in a:
        and_all &= x
        max_val = max(max_val, x)

    k = 0
    if max_val == 0: # 特殊处理最大值为0的情况
        bits = 1
    else:
        bits = max_val.bit_length() # 计算最大值的二进制位数
    
    mask = (1 << bits) - 1      # 创建一个位数限制的掩码
    k = (~and_all) & mask       # 计算最优k值

    max_sum = 0
    for j in range(bits): # 遍历每一位计算贡献
        c_j = 0
        for x in a:
            if (x >> j) & 1:
                c_j += 1
        k_j = (k >> j) & 1
        c_j_final = min(n, c_j + k_j)
        max_sum += c_j_final * (1 << j)
    
    print(max_sum, k)

t = int(input())
for _ in range(t):
    solve()