алгоритм расчета XOR - PullRequest
Новая
       6

алгоритм расчета XOR

2 голосов
/ 20 февраля 2011

Я хочу вычислить XOR чисел от 0 до (n) ^ {1/2} - 1 с каждым из чисел от 0 до (n) ^ {1/2} - 1. Я хочу сделать это в O(n) время и нельзя использовать операции XOR, OR и AND.

Если я знаю XOR для X и Y, могу ли я вычислить XOR для X + 1 и Y в постоянное время?

Как отмечают некоторые, XOR можно рассчитать в постоянное время, используя AND и NOT.Как я могу сделать то же самое для AND?Как рассчитать AND чисел от 0 до (n) ^ {1/2} - 1 с каждым из чисел от 0 до (n) ^ {1/2} - 1. Я хочу сделать это в O (n)время и нельзя использовать операции XOR, OR и AND.

PS - здесь предполагается модель RAM, и операции (сложение, умножение, деление) над

Ответы [ 5 ]

2 голосов
/ 20 февраля 2011

XOR может быть построен с использованием AND и NOT (и комбинируя их для создания NAND). Вы можете использовать AND и NOT?

В C #: 

Func<bool, bool, bool> nand = (p, q) => !(p && q);

Func<bool, bool, bool> xor = (p, q) =>
{
    var s1 = nand(p, q);
    var s2a = nand(p, s1);
    var s2b = nand(q, s1);
    return nand(s2a, s2b);
};

Я подражаю этому: http://en.wikipedia.org/wiki/NAND_logic#XOR

В C # используется модуль, сумма и умножение. (Ограничения: я использую uint, поэтому максимум 32 бита. Это будет работать для ulong, поэтому максимум 64 бита) 

uint a = 16;
uint b = 5;
uint mult = 1;
uint res = 0;

for (int i = 0; i < 32; i++)
{
    uint i1 = a % 2;
    uint i2 = b % 2;

    if (i1 != i2) {
        res += mult;
    }

    a /= 2;
    b /= 2;
    mult *= 2;
}

Где res - ответ.

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

2 голосов
/ 20 февраля 2011

Да.

Начните с сетки [1x1]: 

H(-1) = [ 0 ]

Затем примените рекурсию: 

H(i) = [ H(i-1)           H(i-1)+(1 << i)
         H(i-1)+(1 << i)  H(i-1)          ]

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

2 голосов
/ 20 февраля 2011

Вы можете построить вентиль XOR из NAND (диаграмма здесь ), чтобы вы могли сделать это с помощью оператора if с ! (NOT) и && AND (если мы используем C / C ++ / PHP в качестве примера здесь). Что касается его разработки в постоянное время, то вычисления будут одинаковыми на каждой итерации, поэтому они будут постоянными.

1 голос
/ 24 апреля 2014

если два не равны, то они равны xor. 

xorBits(bit1,bit2){
     return bit1 != bit2?1:0
}

xorBooleans(boolean1,boolean2){
    return boolean1 != boolean2
}
0 голосов
/ 20 февраля 2011

Во-первых, пусть k будет наименьшей степенью 2, большей или равной sqrt (n).k по-прежнему равно O (sqrt (n)), поэтому это не изменит сложности.

Чтобы построить полную таблицу k по k, мы создадим ее по одной строке за раз.

МыНачните с 0-й строки: это легко, потому что 0 xor j = j. 

for i in xrange(k):
    result[0][i] = i

Далее мы перебираем строки в порядке с серым кодом.Серый код - это способ подсчета каждого числа от 0 до единицы меньше степени 2 путем изменения одного бита за раз.

Из-за свойства серого кода мы меняем строкучисло на 1 бит, поэтому мы легко вычисляем новую строку из старой, поскольку xors будет меняться только на 1 бит. 

last = 0
for row in graycount(k):
    if row == 0: continue
    bit_to_change = find_changed_bit(last, row)
    for i in xrange(k):
        result[row][i] = flip_bit(result[last][i], bit_to_change))
    last = row

Нам нужны некоторые функции, которые помогут нам здесь.Сначала функция, которая находит первый бит, который отличается. 

def find_changed_bit(a, b):
    i = 1
    while True:
        if a % 2 != b % 2: return i
        i *= 2
        a //= 2
        b //= 2

Нам нужна функция, которая изменяет бит за O (1) раз. 

def flip_bit(a, bit):
    thebit = (a // bit) % 2
    if thebit:
        return a - bit
    else:
        return a + bit

Наконец, хитрый бит:считая в серых кодах.Из википедии мы можем прочитать, что простой серый код может быть получен путем вычисления xor (a, a // 2). 

def graycount(a):
    for i in xrange(a):
        yield slow_xor(a, a // 2)

def slow_xor(a, b):
    result = 0
    k = 1
    while a or b:
        result += k * (a % 2 == b % 2)
        a //= 2
        b //= 2
        k *= 2
    return result

Обратите внимание, что slow_xor равно O (количество битов в a и b), но это нормально, так как мы не используем его во внутреннем цикле основной функции.

...