9
$\begingroup$

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:

  1. 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}\}$?

  2. Why does the appear to be a recurring pattern in the plots and images below?

offset=284 offset=759 offset=951

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: "And" output

"Or" output "Or" output

"Xor" output "Xor" output

$\endgroup$
6
  • 1
    $\begingroup$ So what do you mean by "probability" with the integers? $\endgroup$ Feb 8, 2015 at 7:20
  • $\begingroup$ @AdamHughes sorry it was awkward phrasing. I meant that for a given range and all possible pairs of integers from that range, what is the percentage of them that, after applying the operations, still is within the range? Feel free to edit the original post. $\endgroup$ Feb 8, 2015 at 16:06
  • $\begingroup$ Is the horizontal axis on the graphs $a$, so for the first graph you are using an interval of $[a,a+284]$? $\endgroup$ Feb 8, 2015 at 18:19
  • $\begingroup$ @RossMillikan Precisely. $\endgroup$ Feb 8, 2015 at 18:20
  • 1
    $\begingroup$ I suspect that it may be productive to talk about this on the whole real line -where we can still define bitwise operation acting on the whole infinite binary expansion. Then, we associate each interval $[a,b]$ with the "area" (i.e. two dimensional measure) of $[a,b]\times[a,b]$ such that $x$ op $y$ is in $[a,b]$. This definition mostly coincides when $a$ and $b$ are integers, but gives arbitrary detail. $\endgroup$ May 13, 2015 at 2:51

1 Answer 1

4
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ Great answer - I'm assuming that the vertical "streaks" in the images (the bottom 3) correspond to 256, 512, etc.? $\endgroup$ Feb 8, 2015 at 18:35
  • $\begingroup$ I'm sure they do. $\endgroup$ Feb 8, 2015 at 20:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .