I thought of a problem today: given a range of integers $[a, b]$, for all pairs of integers $(x, y)$ in that range, what is the number of them such that $x$ op $y \in [a, b]$, where op is one of {xor, and, or} (all bit-wise)? I use this to find the percentage of all possible pairs of integers in the range, when applying the operation, is still in the range. Of course, these operations work on the binary representation of the integers.
I will let $P_{op}([a, b])$ be a value between 0 and 1 which is the percentage of integer pairs $(x, y) \in [a, b] \times [a,b]$ such that $x$ op $y \in [a, b]$.
I have not found any material that finds the probability directly, so I wrote a program to do it for me. However, I am noticing strange behavior. As examples, I provide outputs of some runs, where $b-a \in \{284, 759, 951\}$ (randomly selected). The horizontal axis denotes $a$ (the low end of the range), and the vertical axis denotes the respective $P_{op}$.
It is strange to see that the "or" and "and" plots have somewhat of a recurring pattern, whereas the "xor" plot does not (and stays at 0 for most values).
I'd like to know:
Is there a closed form (or anything more efficient than brute force) to determine, for any interval $[a,b]$, $P_{op}([a,b])$ for op $\in\{\text{or, and, xor}\}$?
Why does the appear to be a recurring pattern in the plots and images below?
Interestingly enough, there does seem to be a pattern! I generated algorithms for every single offset up to some number (~550 here since the algorithm was starting to take a long time) for each of {xor, or, and}, and then generated images displaying them. Each row corresponds to some offset, and each column represents the x-value in the images above (the lower bound of the range).
Since each pixel represents a real value between 0 and 1, I multiplied each value by 255 and mapped them to an integer — a value of 0 is black, 255 is white, and any value in between is linearly scaled. For example, 128 is grey (halfway between white and black).
The patterns look really cool!
"And" output:
"Or" output
"Xor" output
The zero of the XOR on the first graph is easily explained. When $a \gt 256$, either $a$ or $b$ will have at least one of the $512$ or $1024$ bits set. If they both have either one, the XOR is smaller than $a$ and it fails. If they each have one, the XOR is larger than $b$ and it fails. The slight blip around $512$ comes when $a$ is just less than $512$, so has a $256$ bit set and $b$ is greater than $768$, so the XOR is around $512$ and in range. The periodicity in your other plots also depends on binary. Note that the wavelength in the $284$ plot for and and or is $256$