What is the bitwise xor of an interval?

Question

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] $$

Answer 1

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.

Answer 2

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]

Answer 3

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.