6
$\begingroup$

Let $\oplus$ be bitwise xor. Let $k,a,b$ be non-negative integers. $[a..b]=\{x\mid a\leq x, x\leq b\}$, it is called a integer interval.

What is a fast algorithm to find $\{ k\oplus x\mid x\in [a..b]\}$ as a union of set of integer intervals.

One can prove that $[a+k..b-k]\subseteq \{ k\oplus x\mid x\in [a..b]\}$ by showing that $x-y\leq x\oplus y \leq x+y$.

Edit: I should specify the actually input and output to remove ambiguity.

Input: $k, a, b$.

Output: $a_1, b_1, a_2, b_2,\ldots,a_m,b_m$. Such that:

$$ \{ k\oplus x\mid x\in [a..b]\} = \bigcup_{i=1}^m [a_i..b_i] $$

$\endgroup$
7
$\begingroup$

Here's an efficient solution based on BDDs

  1. Find $n$ such that $k,a,b < 2^n$. Create $n$ boolean variables, one for each position in an $n-bit$ number
  2. Write out a boolean formula representing every number in that interval. For example, if $n=4$ (so that we are only considering possible inputs in $[0..15]$), then the interval $[2..4]$ can be written as $\neg x_0 \wedge ((x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (\neg x_1 \wedge x_2))$ -- there is a $0$ in the $8$'s position, and either the next three bits read $100$, or the next two bits read $01$. Note that this is equivalent to partitioning the interval into subintervals aligned with powers of $2$.
  3. Represent the boolean formula as a BDD
  4. Similarly, write $[k..k]$ as a boolean formula. Use standard BDD algorithms to XOR the two BDDs.
  5. Read the intervals out of the BDD. For example, if $n=5$, and we take the path in the BDD corresponding to setting $x_0=1,x_1=0,x_2=1$, and find that we have reached a true leaf (i.e.: a five-digit binary number that starts with 101 is in the set no matter what its lower two digits are), then the interval $[20..23]$ is in the set.

Depending on the application, you might want to leave the set as a BDD rather than reading it out back into intervals, as the BDD representation may be much more compact.

There is also a more elementary and direct solution. Note that XOR'ing by $k$ is equivalent to sequentially XOR'ing by each bit of $k$. Break $k$ into bits, and break $[a..b]$ into subintervals aligned with powers of two, and see what happens to each subinterval. You can work this out, and implement it efficiently using segtrees, but I expect that it will be equivalent to the BDD solution, which is faster and allows for the use of standard libraries.

Analysis

Analyzing BDDs is slightly tricky, but I'll have a go.

$[a..b]$ can be represented using at most $2\lceil\log(b-a)\rceil$ power-of-2-aligned subintervals. I'm not sure how to properly show it, but visualizing the resulting BDD, we see it will have a sort of "triskelion" structure, with size $O(\log(b-a))$.

Let $n=\max(a,b,k)$. XORing each subinterval by $k$ will preserve the subinterval, but may move it. Since each subinterval takes $O(\log n)$ space to represent and there are $O(\log n)$ of them, this lets us bound the size of the resulting BDD as $O((\log n)^2)$. I believe this gives us a $O((\log n)^2)$ bound on the entire operation, but don't quote me on that -- the runtime is proportional to the size of the intermediate BDDs, and I'll have a bit more thinking to do to determine what happens there.

$\endgroup$
4
$\begingroup$

Here is one straightforward algorithm. I'm not sure what the worst case running time is, but it is at most $O(n\log^2 n )$, where $n=\max(a,b,k)$.

  1. Compute the list $[k\oplus a,\ldots,k\oplus b]$.
  2. Split the resulting list into obvious intervals, by merging adjacent entries whenever they form an interval, and creating a new interval when they don't.
  3. Sort the resulting list of intervals. (This takes potentially $O(n\log n)$ steps, where each comparison is $O(\log n)$.)
  4. Merge adjacent intervals.

Here is the algorithm in Haskell:

import Data.Bits
import Data.List

-- implements step 2
split (a:as) = split_ (a,a) as
    where split_ (c,d) [] = [(c,d)]
          split_ (c,d) (e:list) | e == d + 1 = split_ (c,e) list
                                | otherwise  = (c,d) : split_ (e,e) list

-- implements step 4
merge (a:as) = merge_ a as
    where merge_ (c,d) [] = [(c,d)]
          merge_ (c,d) ((e,f):list) | e == d + 1 = merge_ (c,f) list
                                    | otherwise  = (c,d) : merge_ (e,f) list

intervals k a b 
  = merge $ sortBy (\(a,b) (c,d) -> compare a c) $ split $ map (\x -> xor k x) [a..b]
$\endgroup$
  • $\begingroup$ Using a general-purpose sorting algorithm, this will take the full $O(n\log n)$. There will be no nontrivial intervals upon XOR'ing by $1$. Of course, this list has a special structure (it will look like e.g.: [1,0,3,2,5,4]), and can be sorted in linear time. It is more accurate to call the running time pseudo-supralinear, as the input list is not written out in full. Its actual running time is $O(n^n)$ $\endgroup$ – James Koppel Jun 24 '12 at 20:14
  • $\begingroup$ @JamesKoppel: I don't see that I'm only sorting a list of length $n$ and I only do this once. All other steps are $O(n)$. $\endgroup$ – Dave Clarke Jun 24 '12 at 20:15
  • $\begingroup$ Sorry; accidentally posted comment unfinished. $\endgroup$ – James Koppel Jun 24 '12 at 20:18
  • $\begingroup$ I don't see how it will be $O(n^n)$. I don't know what pseudo-supralinear time is. Even if there are no non-trivial intervals, the worst case scenario is that I will have $n$ singleton intervals in the list at the end of step 3. $\endgroup$ – Dave Clarke Jun 24 '12 at 20:22
  • $\begingroup$ I think James was trying to say the input is only 3 integers: $k, a$ and $b$. I updated my question to remove the ambiguity. $\endgroup$ – Chao Xu Jun 24 '12 at 20:41
2
$\begingroup$

This should be a comment to the nice answer by @JamesKoppel but it is too large for a comment:

I don't think that the size of the BDD for $[a \ldots b]$ is $O(\log (b-a))$ because even to test if the $n$ Boolean input variables are equal to a fixed constant requires linear size BDD size in the number of variables, i.e. here $O(\log n)$. Similar to your idea in 2., it is possible to show that the size of the BDD for $[a \ldots b]$ has also linear size and can be efficiently constructed (i.e. in linear time according to the BDD size), see e.g. here for the construction and proof idea.

According to the running time: You have one XOR operation on BDDs of size $O(\log n)$. The running time for a XOR operation (and also the size of the resulting BDD) is in the order of the product of the sizes of the involved BDDs, i.e. overall we have a running time of $O(\log^2 n)$. A good reference about the complexity of such operations is the book Branching Programs and Binary Decision Diagrams by Ingo Wegener.

I do not want to go into detail but I think the last step is a little bit more complex than you describe. But I think it can be done in time $O(\log^2 n)$ (i.e. linear to the BDD size) to get the pattern of the 1-inputs and then you need $O(m)$ time to output the intervals.

$\endgroup$
  • $\begingroup$ What is $m$ in the last line? $\endgroup$ – Dave Clarke Jun 25 '12 at 11:50
  • $\begingroup$ @DaveClarke: The number of intervals for the output (I adopted the notation used in the question). $\endgroup$ – Marc Bury Jun 25 '12 at 12:29
  • $\begingroup$ Oops. Can one read them off in $O(m)$, given that $m$ is unknown? $\endgroup$ – Dave Clarke Jun 25 '12 at 12:30
  • $\begingroup$ Maybe it is $O(m \log n)$ :) The last step is a little bit tricky. Maybe I edit my answer to give a more detailed description if you are interested in :) $\endgroup$ – Marc Bury Jun 25 '12 at 12:41
  • 1
    $\begingroup$ The whole matter is subtle (and ingenious). My slow Haskell program has the virtue of being more direct. $\endgroup$ – Dave Clarke Jun 25 '12 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.