问使用位XOR运算符直接计算递归中的元素

EN

让我们画出矩阵A的前16行和列：

1000000000000000
1111111111111111
1010101010101010
1100110011001100
1000100010001000
1111000011110000
1010000010100000
1100000011000000
1000000010000000
1111111100000000
1010101000000000
1100110000000000
1000100000000000
1111000000000000
1010000000000000
1100000000000000

你的问题“是否有模式”的答案非常清楚“是的！”左上角的8x8子矩阵被直接复制到自己下面，也被直接复制到右边，除了右上角的拷贝在左上角有0，而不是1。右下角的8x8子矩阵都是0，但左上角有1。如果我们只研究前8行和前8列，就会出现完全相同的模式：

10000000
11111111
10101010
11001100
10001000
11110000
10100000
11000000

左上角的4x4子矩阵被直接复制到自己下面，也直接复制到右边，除了右边的拷贝左上角有0，而不是1。右下角的4x4子矩阵都是0，但左上角有一个1。

这种递归的自相似性使得矩阵A成为一个分形，非常类似于Sierpinski三角形.

递归自相似性还使我们能够使用i和j的二进制表示轻松地计算Ai。设B是i或j的二进制表示中的最高阶位集。然后，以下过程将返回Ai的正确值。

• 对于b=B到0：
  • 如果j=0限制为0到b，则返回1(我们位于第一列，即全部为1)。
  • 如果将i=0限制为0到b，则返回0(我们位于第一行)。
  • 否则，如果i和j都将1存储在位b中，则返回0，除非每一位中的所有剩余位都为0，在这种情况下返回1。
  • 否则继续(我们递归到一个较小的子矩阵)

​

该算法运行在O(log(max(i，j)运行时，比朴素方法的O(ij)运行时快得多。

让我们通过几个例子来看看这个算法的作用：

• A9 =0来自上面的矩阵。在二进制表示中，i= 1001和j= 1001。它们都在最重要的位中有一个1，并且在那个位之后设置了一些位，所以按照上面的规则，我们返回0。
• A9 =1来自上面的矩阵。在二进制表示中，i= 1001和j= 0011。在最左边(最重要的位)，我有1，j有0。因此，我们继续到下一个位(递归)，其中两者都有一个0。我们再次进入下一位，这里我有0，j有1，因此我们继续到最后一位。两者都在位中有一个1，而下面的所有位都是0(这在很小程度上是正确的，因为没有下面的位)，所以我们返回1。
• A9 =1来自上面的矩阵。在二进制表示中，i= 1001和j= 0100。在最左边(最重要的位)，我有1，j有0。因此，我们继续到下一个位(recurse)，其中我有一个0，j有一个1。我们再次继续到下一个位，其中两个都有一个0。J在这个和下面的所有位中都有0，所以我们返回1。

该算法的一个有趣的含义是，每一行k(对于k> 0)都有一个周期为2^B的重复模式，其中B是行号二进制表示中最重要的部分。例如，第3行(二进制表示11)重复1100，而第9行(二进制表示1001)重复1111111100000000。这意味着行k>0的完整重复序列可以在O(k)存储中表示，并可以通过分别计算j= 0，1，…，2^log_2( k)-1的Ak，j来计算O(k log k)时间。