algorithm to calculate AND

Question

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.

Very similar to stackoverflow.com/questions/5056949/algorithm-to-calculate-xor but not actually a duplicate. — Albin Sunnanbo
– Albin Sunnanbo, Commented Feb 20, 2011 at 13:15
@oil charlesworth Yeah. O(n) sized table is allowed. But building it should be possible in O(n) time — Nitin Garg
– Nitin Garg, Commented Feb 20, 2011 at 13:26
@Nitin: So, "no" then! What you've just described is no lookup table and O(n) storage complexity! — Oliver Charlesworth
– Oliver Charlesworth, Commented Feb 20, 2011 at 13:28

Oliver Charlesworth · Accepted Answer · 2011-02-20 13:53:37Z

2

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.

edited Feb 20, 2011 at 13:53

answered Feb 20, 2011 at 13:22

Oliver Charlesworth

274k34 gold badges591 silver badges687 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Nitin Garg Over a year ago

Is the determinant of matrix our answer according to you?

Oliver Charlesworth Over a year ago

@Nitin: No, the whole matrix is the answer! You were after a 2D array of results, right?

Nitin Garg Over a year ago

ohk ..so H(i-1)+(1 << i) means H(i-1)+ 1 shifted to left by i X Identity matrix?

Oliver Charlesworth Over a year ago

@Nitin: Yes, I guess my notation wasn't amazingly clear. But that's what I meant!

Collectives™ on Stack Overflow

algorithm to calculate AND

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related