algorithm to calculate AND

I want to calculate AND of numbers from 0 to (n)^{1/2} - 1 with each of the numbers from 0 to (n)^{1/2} - 1. I want to do this in O(n) time and can't use the XOR, OR, AND operations.

Specifically, can I calculate X+1 AND Y if I know 开发者_开发问答X AND Y?

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)
         H(i-1)  H(i-1)+(1 << i) ]

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.