计算 AND 的算法

Question

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

具体来说，我可以计算X+1 AND Y吗？如果我知道X AND Y ？

附言- 此处假定 RAM 模型并对 < log(n) 进行运算(加、乘、除)比特数可以做到是常数时间。

Answer 1

是的。

从 [1x1] 网格开始:

H(-1) = [ 0 ]

然后应用递归:

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

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