Как ефективно да се изчисли сумата от побитовите xor стойности на цялата отделна комбинация от дадените числа?

Трябва да изчислите около 1e12 xors, за да направите това грубо. Съвременните процесори могат да извършват около 1 до 10 такива операции в секунда. Така че грубата сила не може да работи; следователно те търсят вас, за да разберат по-добър алгоритъм.

Така че трябва да намерите начин да определите отговора, без да изчислявате всички тези xor.

Съвет: можете ли да измислите начин да го направите, ако всички въведени числа са нула или единица (един бит)? И след това да го разширим до числа от два бита, три бита и т.н.?

Когато оптимизирате кода си, можете да отидете по 3 различни маршрута:

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

Може много добре да има по-бърз математически начин за xoring всяка комбинация от двойки и след това да ги сумирате, но аз не знам. Във всеки случай, на съвременните процесори в най-добрия случай ще спестите микросекунди; това е така, защото извършвате основни операции (xor и sum).

Оптимизирането на архитектурата също няма смисъл. Обикновено става важно при повтарящо се разклоняване, тук нямате нищо подобно.

Най-големият проблем във вашия алгоритъм е четенето от стандартния вход. Въпреки факта, че "scanf" отнема само 5 знака във вашия компютърен код, на машинен език това е по-голямата част от вашата програма. За съжаление, ако данните действително се променят всеки път, когато изпълнявате кода си, няма начин да заобиколите изискването за четене от stdin и няма да има разлика дали използвате scanf, std::cin >> или дори ще се опитате да приложите свой собствен метод за чете символи от входа и ги преобразува в int.

Всичко това предполага, че не очаквате човешко същество да въведе хиляди числа за по-малко от една секунда. Предполагам, че можете да стартирате кода си чрез: 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).