Найти уникальный бит в коллекции чисел - PullRequest
2 голосов
/ 27 ноября 2011

Лучший способ объяснить это - демонстрация.

Есть коллекция номеров. Они могут повторяться, поэтому:

1110, 0100, 0100, 0010, 0110 ...

Номер, который я ищу, это тот, у которого установлен бит, которого нет ни в одном другом. Результатом является число (в данном случае 1 - первое число) и позиция бита (или маска в порядке), то есть 1000 (4-й бит). Может быть более одного решения, но для этого оно может быть жадным.

Я могу сделать это итерацией ... Для каждого числа N это:

N & ~ (другие номера ИЛИ вместе)

Но природа битов в том, что всегда есть лучший метод, если вы мыслите нестандартно. Например, числа экземпляров, которые появляются более одного раза, никогда не будут иметь уникальный бит и не будут влиять на ORing.

Ответы [ 4 ]

5 голосов
/ 27 ноября 2011

Вам просто нужно записать, был ли каждый бит просмотрен один или несколько раз и был ли он просмотрен дважды или более.Уникальные биты - это те, которые были замечены один или несколько раз, а не дважды или более.Это можно сделать эффективно, используя побитовые операции.

count1 = 0
count2 = 0

for n in numbers:
    count2 |= count1 & n
    count1 |= n

for n in numbers:
    if n & count1 & ~count2:
        return n

Если вы не хотите перебирать числа дважды, вы можете отслеживать какое-то число, которое вы видели и которое содержит каждый бит.Это может быть хорошей оптимизацией, если числа хранятся на диске, поэтому для их потоковой передачи необходим доступ к диску, но, конечно, это усложняет код.

examples = [-1] * wordsize
count1 = 0
count2 = 0

for n in numbers:
    if n & ~count1:
        for i in xrange(wordsize):
            if n & (1 << i):
                examples[i] = n
    count2 |= count1 & n
    count1 |= n

for i in xrange(wordsize):
    if (count1 & ~count2) & (1 << i):
        return examples[i]

Вы можете использовать трюки для извлеченияБитовые индексы более эффективны в цикле, который устанавливает примеры, но так как этот код выполняется в большинстве случаев «размер слова», это, вероятно, не стоит.

Этот код легко переводится на C ... Я только что написал на Pythonдля наглядности.

2 голосов
/ 27 ноября 2011

(длинная версия того, что я написал в комментарии)

Посчитав, сколько раз бит в индексе k равен единице для каждого k (есть способ сделать это быстрее, чем наивно, ноэто все еще O (n)), вы получаете список счетчиков bitlength, в которых счетчик 1 означает, что бит был только один раз.Индекс этого счетчика (найденный в O (1), потому что у вас есть фиксированное количество битов), следовательно, битовая позиция, которую вы хотите.Чтобы найти число с установленным битом, просто повторите итерацию всех чисел и проверьте, не установлен ли этот бит снова (O (n)), если это так, то это число, которое вы хотите.

Всего:O (n) против O (n 2 ) проверки каждого числа против всех остальных.

1 голос
/ 27 ноября 2011

Этот метод использует менее 2 проходов (но изменяет входной массив)

    #include <stdio.h>

    unsigned array[] = { 0,1,2,3,4,5,6,7,8,16,17 };
    #define COUNTOF(a) (sizeof(a)/sizeof(a)[0])
    void swap(unsigned *a, unsigned *b)
    {
        unsigned tmp;
        tmp = *a;
        *a = *b;
        *b = tmp;
    }

    int main(void)
    {
    unsigned idx,bot,totmask,dupmask;

    /* First pass: shift all elements that introduce new bits into the found[] array.
    ** totmask is a mask of bits that occur once or more
    ** dupmask is a mask of bits that occur twice or more
    */
    totmask=dupmask=0;
     for (idx=bot=0; idx < COUNTOF(array); idx++) {
         dupmask |= array[idx] & totmask;
         if (array[idx] & ~totmask) goto add;
         continue;

    add:
        totmask |= array[idx];
        if (bot != idx) swap(array+bot,array+idx);
        bot++;
        }
    fprintf(stderr, "Bot=%u, totmask=%u, dupmask=%u\n", bot, totmask, dupmask );

    /* Second pass: reduce list of candidates by checking if
    ** they consist of *only* duplicate bits */
    for (idx=bot; idx-- > 0 ; ) {
        if ((array[idx] & dupmask) == array[idx]) goto del;
        continue;
    del:
        if (--bot != idx) swap(array+bot,array+idx);

    }

    fprintf(stdout, "Results[%u]:\n", bot );
    for (idx=0; idx < bot; idx++) {
        fprintf(stdout, "[%u]: %x\n" ,idx, array[idx] );
        }
    return 0;
    }  

ОБНОВЛЕНИЕ 2011-11-28 Другая версия, которая не изменяет исходный массив. (Временные) результаты хранятся в отдельном массиве.

#include <stdio.h>
#include <limits.h>
#include <assert.h>

unsigned array[] = { 0,1,2,3,4,5,6,7,8,16,17,32,33,64,96,128,130 };
#define COUNTOF(a) (sizeof(a)/sizeof(a)[0])
void swap(unsigned *a, unsigned *b)
{
    unsigned tmp;
    tmp = *a, *a = *b, *b = tmp;
}


int main(void)
{
unsigned idx,nfound,totmask,dupmask;
unsigned found[sizeof array[0] *CHAR_BIT ];

/* First pass: save all elements that introduce new bits to the left
** totmask is a mask of bits that occur once or more
** dupmask is a mask of bits that occur twice or more
*/
totmask=dupmask=0;
 for (idx=nfound=0; idx < COUNTOF(array); idx++) {
     dupmask |= array[idx] & totmask;
     if (array[idx] & ~totmask) goto add;
     continue;

add:
    totmask |= array[idx];
    found[nfound++] = array[idx];
    assert(nfound <= COUNTOF(found) );
    }
fprintf(stderr, "Bot=%u, totmask=%u, dupmask=%u\n", nfound, totmask, dupmask );

/* Second pass: reduce list of candidates by checking if
** they consist of *only* duplicate bits */
for (idx=nfound; idx-- > 0 ; ) {
    if ((found[idx] & dupmask) == found[idx]) goto del;
    continue;
del:
    if (--nfound != idx) swap(found+nfound,found+idx);

}

fprintf(stdout, "Results[%u]:\n", nfound );
for (idx=0; idx < nfound; idx++) {
    fprintf(stdout, "[%u]: %x\n" ,idx, found[idx] );
    }
return 0;
}
0 голосов
/ 27 ноября 2011

Как указано, это не работает:

Вы можете XOR собрать вместе цифры, в результате вы получите mask. И тогда вы должны найти первое число, которое не дает 0 для выражения N & mask.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...