Задать вопрос
  • Алгоритм нахождения чисел без пар из большого потока данных?

    jcmvbkbc
    @jcmvbkbc
    "I'm here to consult you" © Dogbert
    uint32_t xor_all = 0;
    uint32_t xor_bit[32] = {0};
    
    ....
    
    for (i = 0; i < n; ++i) {
        xor_all ^= in;
        for (j = 0; j < 32; ++j) {
            if (in & (1 << j))
                xor_bit[j] ^= in;
        }
    }
    
    for (j = 0; j < 32; ++j) {
        if (xor_all & (1 << j)) {
            out1 = xor_bit[j];
            out2 = xor_all ^ xor_bit[j];
            break;
        }
    }
    
    


    Идея в том, что непарные числа должны различаться хотя бы одним битом.
    Мы будем кроме общего ксора тащить по одному ксору для чисел, имеющих i-й бит установленным.
    В конце общий ксор даст нам различающиеся биты, по одному из которых мы найдём одно из непарных чисел, а там и второе.
    Ответ написан
    4 комментария