алгоритм для расчета И

Question

Я хочу вычислить И чисел от 0 до (n)^{1/2} - 1 с каждым из чисел от 0 до (n)^{1/2} - 1. Я хочу сделать это в O(n) времени и не могу использовать операции XOR, OR и AND.

В частности, можно ли рассчитать X+1 AND Y, если я знаю X AND Y?

P.S. - Здесь предполагается модель ОЗУ и операции (сложение, умножение, деление) над < log(n) битовыми числами могут выполняться в постоянное время.

Answer 1

Да.

Начните с сетки [1x1]:

H(-1) = [ 0 ]

Затем примените рекурсию:

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

, где это означает сцепление матрицы.т.е. каждая рекурсия удваивает размер сетки в каждом измерении.Повторяйте, пока не получите нужный размер.