3
$\begingroup$

Is there an efficient way to find two positive integers given their bitwise exclusive or and product?

I saw this on quora, and wasn't able to come up with a good solution. Ideally, I would like a O(1) or O(number of bits) algorithm

An obvious way is to factor the product, using the xor to bound the factors, and seeing which factors when xored give the desired xor.

Also, I'm not sure what tags this should use besides factoring.

$\endgroup$
2
  • 1
    $\begingroup$ You should specify what you mean by 'xor'. I assume you mean the xor of their binary expressions, but we don't assume that on math.stackexchange. $\endgroup$
    – JonathanZ
    Nov 24, 2019 at 1:09
  • $\begingroup$ Done. Good point. $\endgroup$ Nov 24, 2019 at 2:26

0

You must log in to answer this question.

Browse other questions tagged .