2

我想计算从 0 到 (n)^{1/2} - 1 的数字的 XOR，每个数字从 0 到 (n)^{1/2} - 1。我想在 O(n) 中执行此操作time 并且不能使用 XOR、OR 和 AND 操作。

如果我知道 X 和 Y 的 XOR，我可以在恒定时间内计算 X+1 和 Y 的 XOR 吗？

正如一些人指出的那样，可以使用 AND 和 NOT 在恒定时间内计算 XOR。我如何为 AND 做同样的事情？我如何计算从 0 到 (n)^{1/2} - 1 的数字与从 0 到 (n)^{1/2} - 1 的每个数字的 AND。我想在 O(n) 中执行此操作time 并且不能使用 XOR、OR 和 AND 操作。

PS - 这里假设 RAM 模型，并且可以在恒定时间内完成对 < log(n) 位数的操作（加法、乘法、除法）。

4

5 回答 5

2

是的。

从 [1x1] 网格开始：

H(-1) = [ 0 ]

然后应用递归：

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

其中表示矩阵连接。即每次递归都会使每个维度中的网格大小加倍。重复直到达到所需的大小。

于 2011-02-20T13:46:00.193 回答
2

您可以从 NAND 构建一个 XOR 门（此处的图表），因此您可以使用带有(NOT) 和AND 的if语句来完成此操作（如果我们在这里使用 C/C++/PHP 作为示例）。至于在恒定时间内计算出来，每次迭代的计算都是一样的，所以它是恒定的。!&&

于 2011-02-20T12:16:52.100 回答
2

可以使用 AND 和 NOT 构建 XOR（并将它们组合起来构建 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 是响应。

模数可以建立在除法、乘法和减法之上。

于 2011-02-20T12:19:14.303 回答
1

如果两者不相等，则它们是异或。

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

xorBooleans(boolean1,boolean2){
    return boolean1 != boolean2
}
于 2014-04-24T15:40:27.980 回答
0

首先，设 k 为大于或等于 sqrt(n) 的 2 的最小幂。k 仍然是 O(sqrt(n)) 所以这不会改变复杂性。

为了构造完整的 k by k 表，我们一次构造一行。

我们从第 0 行开始：这很容易，因为 0 xor j = j。

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

接下来，我们按格雷码顺序遍历行。格雷码是一种通过一次更改一位来计算从 0 到小于 2 的幂的每个数字的方法。

由于格雷码属性，我们将行号更改 1 位，因此我们可以轻松地从旧行计算新行，因为 xor 只会更改 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

最后，棘手的一点：格雷码计数。从 wikipedia 中，我们可以读到一个简单的格雷码可以通过计算 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 中的位数），但这没关系，因为我们没有在 main 函数的内部循环中使用它。

于 2011-02-20T14:15:30.763 回答