CODEWITHSUNDEEP
algorithmxor
Vikash Balasubramanian
Vikash Balasubramanian

Reputation: 3233

Algorithm: constrained XOR of numbers within a range

Let us say we are given a number n. We need to find the number of values S ^ (S+n) lying in the range [L, R]. (Where S is any non-negative integer and ^ is the bitwise xor operator).

I can easily do this if n is power of two (they have a very useful pattern)

I am not sure how to solve this for any general n. Any suggestions?

EDIT:

n is also a non-negative integer. n, L, R are all less than 10^18.

This was a programming question in some practice test which i gave sometime back, i just remembered this seeing a similar question in StackOverflow today.

EDIT 2: Explaining with an example, say n = 1. Then we know that S ^ (S + 1) will always have a binary representation of all ones. eg: 1,3,7,...

So solving this is easy we just have to count the number of such numbers within the Range [L,R] it is quite simple.

For n = any power of 2 similar methods work. But i have no idea what to do if n is not a power of 2.

Upvotes: 1

Views: 297

Answers (1)

WhatsUp
WhatsUp

Reputation: 1636

Let C(n) be the (infinite) set of numbers that can be written as S ^ (S + n) for some S.

We have the following recurrence relations on the sets C(n):

  • If n = 2k is even, then C(n) = {2x : x in C(k)};
  • If n = 2k + 1 is odd, then C(n) = {2x + 1 : x in C(k)} union {2x + 1 : x in C(k + 1)}.

An algorithm can be deduced from these relations. More precisely, a pair (C(n), C(n + 1)) can be deduced from (C(n / 2), C(n / 2 + 1)). Note that the union above is really a disjoint union, because every element in C(n) has the same parity as n, hence C(k) and C(k + 1) do not intersect.

Proof of the recurrence relations:

Simply look at the last binary digits of n and S.

Upvotes: 2

Related Questions