Here's an efficient solution based on BDDs
- Find $n$ such that $k,a,b < 2^n$. Create $n$ boolean variables, one for each position in an $n-bit$ number
- 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$.
- Represent the boolean formula as a BDD
- Similarly, write $[k..k]$ as a boolean formula. Use standard BDD algorithms to XOR the two BDDs.
- 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.