I want to calculate XOR of numbers from 0 to (n)^{1/2} - 1 with each of numbers from 0 to (n)^{1/2} - 1. i want to do this in O(n) time and cant use the XOR, OR, AND operations.
If i know the XOR of X and Y, can i calculate XOR of X+1 and Y in constant time?
As some have pointed out that XOR can be calculated in constant time using AND and NOT. How do i do the same for AND? How do i calculate AND of numbers from 0 to (n)^{1/2} - 1 with each of numbers from 0 to (n)^{1/2} - 1. i want to do this in O(n) time and cant use the XOR, OR, AND operations.
P.S. - RAM model is being assumed here and operations (add, multiply, divide) on < log(n) bit numbers can be done is constant time.
Yes.
Start with a [1x1] grid:
H(-1) = [ 0 ]
Then apply the recursion:
H(i) = [ H(i-1) H(i-1)+(1 << i)
H(i-1)+(1 << i) H(i-1) ]
where that denotes matrix concatenation. i.e. each recursion doubles the size of the grid in each dimension. Repeat until you achieve the required size.