[Solved]: What is the bitwise xor of an interval?

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 $2lceillog(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.