Эффективный метод получения одного номера, который не может быть создан из любой комбинации XORing

Ответ 1

Каждое число можно рассматривать как вектор в векторном пространстве (Z/2) ^ 64 над Z/2. Вы в основном хотите знать, если заданные векторы охватывают все пространство, а если нет, то для создания одного не натянутого (за исключением того, что span всегда включает нулевой вектор - для этого вам понадобится специальный случай, если вы действительно хотите один или несколько), Это может быть достигнуто путем устранения Гаусса.

В этом конкретном векторном пространстве устранение Гаусса довольно просто. Начните с пустого набора для основы. Делайте следующее, пока не будет больше номеров. (1) Отбросьте все числа, равные нулю. (2) Сканирование младших бит набора оставшихся номеров (младший бит для x - x & ~(x - 1)) и выберите один с битом младшего разряда. (3) Положите это в основу. (4) Обновите все остальные номера с помощью того же бита, установленного с помощью XORing с новым базовым элементом. Никакое оставшееся число не имеет этого бита или бит младшего разряда, поэтому мы заканчиваем после 64 итераций.

В конце, если есть 64 элемента, то подпространство - это все. В противном случае мы отправили меньше 64 итераций и немного пропустили: число с только этим битом не было натянуто.

К нулевому случаю: нуль является опцией тогда и только тогда, когда мы никогда не выбрасываем число (т.е. входные векторы независимы).

Пример над 4-разрядными номерами

Начните с 0110, 0011, 1001, 1010. Выберите 0011, потому что у него установлены бит. Основа теперь {0011}. Другими векторами являются {0110, 1010, 1010}; обратите внимание, что первый 1010 = 1001 XOR 0011.

Выберите 0110, потому что он имеет бит бит бит. Базис теперь {0011, 0110}. Другими векторами являются {1100, 1100}.

Выберите 1100. Базис теперь {0011, 0110, 1100}. Другие векторы - {0000}.

Бросьте 0000. Мы закончили. Мы пропустили бит высокого порядка, поэтому 1000 не находится в промежутке.

Ответ 2

Как отмечает рэп-музыка, вы можете думать о проблеме как о поиске базы в векторном пространстве. Тем не менее, нет необходимости фактически полностью его решать, просто найти, можно ли это сделать или нет, а если нет: укажите примерное значение (то есть двоичный вектор), который не может быть описан в терминах поставленного набора,

Это можно сделать в O (n ^ 2) в терминах размера входного набора. Это следует сравнить с <сильным > исключением Гаусса, которое является O (n ^ 3), http://en.wikipedia.org/wiki/Gaussian_elimination.

64 бит вообще не проблема. С примером кода python ниже 1000 бит с набором с 1000 случайными значениями от 0 до 2 ^ 1000-1 занимает около секунды.

Вместо того, чтобы выполнять удаление Гаусса, достаточно, чтобы выяснить, можем ли мы переписать матрицу всех битов треугольной формы, например: (для 4-разрядной версии:)

 original        triangular
 1110 14         1110 14
 1011 11          111  7
  111  7           11  3
   11  3            1  1
    1  1            0  0

Решение работает следующим образом: сначала все исходные значения с одним и тем же самым значимым битом помещаются вместе в список списков. Для нашего примера:

 [[14,11],[7],[3],[1],[]]

Последняя пустая запись означает, что в исходном списке не было нулей. Теперь возьмем значение из первой записи и заменим эту запись списком, содержащим только этот номер:

 [[14],[7],[3],[1],[]]

а затем сохраните xor сохраненного номера со всеми удаленными записями в нужном месте в векторе. Для нашего случая имеем 14 ^ 11 = 5, поэтому:

 [[14],[7,5],[3],[1],[]]

Фокус в том, что нам не нужно сканировать и обновлять все остальные значения, просто значения с одним и тем же самым значимым битом.

Теперь обработайте элемент 7,5 таким же образом. Держите 7, добавьте 7 ^ 5 = 2 в список:

 [[14],[7],[3,2],[1],[]]

Теперь 3,2 покидает [3] и добавляет 1:

 [[14],[7],[3],[1,1],[]]

И 1,1 уходит [1] и добавляет 0 к последней записи, допускающей значения без заданного бита:

 [[14],[7],[3],[1],[0]]

Если в конце вектор содержит по крайней мере одно число в каждом векторном элементе (как в нашем примере), база завершена и любое число подходит.

Здесь полный код:

# return leading bit index ir -1 for 0.
# example 1 -> 0
# example 9 -> 3
def leadbit(v):
    # there are other ways, yes...
    return len(bin(v))-3 if v else -1

def examinebits(baselist,nbitbuckets):
    # index 1 is least significant bit. 
    # index 0 represent the value 0    
    bitbuckets=[[] for x in range(nbitbuckets+1)]  
    for j in baselist:
        bitbuckets[leadbit(j)+1].append(j)   
    for i in reversed(range(len(bitbuckets))):
        if bitbuckets[i]:
            # leave just the first value of all in bucket i
            bitbuckets[i],newb=[bitbuckets[i][0]],bitbuckets[i][1:]
            # distribute the subleading values into their buckets
            for ni in newb: 
                q=bitbuckets[i][0]^ni
                lb=leadbit(q)+1
                if lb:
                    bitbuckets[lb].append(q)
                else:
                    bitbuckets[0]=[0]
        else:
            v=2**(i-1) if i else 0
            print "bit missing: %d. Impossible value: %s == %d"%(i-1,bin(v),v)
            return (bitbuckets,[i])    
    return (bitbuckets,[])

Пример использования: (8 бит)

import random
nbits=8
basesize=8
topval=int(2**nbits)
# random set of values to try:
basel=[random.randint(0,topval-1) for dummy in range(basesize)]
bl,ii=examinebits(basel,nbits)

bl теперь является треугольным списком значений, вплоть до того момента, когда это было невозможно (в этом случае). Пропущенный бит (если таковой имеется) находится в ii [0].

Для следующего испытанного набора значений: [242, 242, 199, 197, 177, 177, 133, 36] треугольная версия:

base value: 10110001 177
base value:  1110110 118
base value:   100100 36
base value:    10000 16
first missing bit: 3 val: 8
( the below values where not completely processed )
base value:       10 2
base value:        1 1
base value:        0 0

Вышеприведенный список был напечатан следующим образом:

for i in range(len(bl)):
    bb=bl[len(bl)-i-1]
    if ii and len(bl)-ii[0] == i:
        print "example missing bit:" ,(ii[0]-1), "val:", 2**(ii[0]-1)
        print "( the below values where not completely processed )"
    if len(bb):
        b=bb[0]
        print ("base value: %"+str(nbits)+"s") %(bin(b)[2:]), b