Как эффективно рассчитать сумму побитовых значений xor всех различных комбинаций заданных чисел?

Вам нужно вычислить около 1e12 xors, чтобы переборщить это. Современные процессоры могут выполнять около 1e10 таких операций в секунду. Так что грубая сила не может работать; поэтому они ищут вас, чтобы найти лучший алгоритм.

Поэтому вам нужно найти способ определить ответ, не вычисляя все эти xors.

Подсказка: можете ли вы придумать способ сделать это, если все входные числа были либо нулем, либо единицей (один бит)? А затем распространить его на двухбитные, трехбитные числа и так далее?

При оптимизации кода вы можете пойти тремя разными путями:

1. Оптимизация алгоритма.
2. Оптимизация вызовов языковых и библиотечных функций.
3. Оптимизация под конкретную архитектуру.

Вполне может быть, что существует более быстрый математический способ сортировки каждой комбинации пар, а затем их суммирования, но я этого не знаю. В любом случае, на современных процессорах вы в лучшем случае сократите микросекунды; это потому, что вы выполняете основные операции (xor и sum).

Оптимизация под архитектуру также не имеет большого смысла. Обычно это становится важным при повторяющихся ветвлениях, здесь у вас ничего подобного нет.

Самая большая проблема в вашем алгоритме — это чтение со стандартного ввода. Несмотря на то, что "scanf" занимает всего 5 символов в вашем компьютерном коде, на машинном языке это основная часть вашей программы. К сожалению, если данные на самом деле будут меняться каждый раз, когда вы запускаете свой код, нет никакого способа обойти требование чтения из стандартного ввода, и не будет никакой разницы, используете ли вы scanf, std::cin >> или даже попытаетесь реализовать свой собственный метод для читать символы из ввода и преобразовывать их в целые числа.

Все это предполагает, что вы не ожидаете, что человек введет тысячи чисел менее чем за одну секунду. Я думаю, вы можете запустить свой код через: myprogram < data.

Эта функция растет квадратично (спасибо @rici). Около 25 000 положительных целых чисел, каждое из которых равно 999 999 (в худшем случае), вычисление цикла for само по себе может завершиться примерно за секунду. Попытка заставить это работать с вводом, как вы указали, и для 1 миллиона положительных целых чисел просто не представляется возможным.

С подсказкой в ​​​​ответе Алана Стоукса у вас может быть линейная сложность вместо квадратичной со следующим:

std::size_t xor_sum(const std::vector<std::uint32_t>& v)
{
    std::size_t res = 0;

    for (std::size_t b = 0; b != 32; ++b) {
        const std::size_t count_0 =
            std::count_if(v.begin(), v.end(),
                          [b](std::uint32_t n) { return (n >> b) & 0x01; });
        const std::size_t count_1 = v.size() - count_0;
        res += count_0 * count_1 << b;
    }
    return res;
}

Текущая демонстрация.

Объяснение:

• x^y = Sum_b((x&b)^(y&b)), где b — однобитовая маска (от 1<<0 до 1<<32).
• Для данного бита с count_0 и count_1 соответствующими номерами подсчета чисел с битом, установленным на 0 или 1, мы имеем count_0 * (count_0 - 1) 0^0, count_0 * count_1 0^1 и count_1 * (count_1 - 1) 1^1 (а 0^0 и 1^1 равны 0).