Improving Interval Conditions

Checking if a certain number $$x$$ falls into a given range between $$a$$ and $$b$$ is a quite easy task:

$a \leq x \leq b$

which can be implemented by taking the interval apart:

$a <= x \&\& x <= b$

What if $$a$$ and $$b$$ share common terms? You could change the condition in a way of balancing the terms over the equation in order to minimize the number of operations needed. The cool thing is, you can re-format an interval check as an expression with an absolute value and might be lucky to reduce the number of operations even further. Here is how it's done. Let $$a, b, x \in\mathbb{R}$$:

$\begin{array}{rl}& a \leq x \leq b\\\Leftrightarrow & 0 \leq x - a \leq b - a\\\Leftrightarrow & -\frac{b-a}{2} \leq x-a-\frac{b-a}{2} \leq \frac{b-a}{2}\\\Leftrightarrow & -\frac{b-a}{2} \leq x-a-\frac{b-a}{2} \land x-a-\frac{b-a}{2} \leq \frac{b-a}{2}\\\Leftrightarrow & -(x-a-\frac{b-a}{2}) \leq \frac{b-a}{2} \land x-a-\frac{b-a}{2} \leq \frac{b-a}{2}\\\Leftrightarrow & |x-a-\frac{b-a}{2}| \leq \frac{b-a}{2}\\\Leftrightarrow & |2(x-a)-(b-a)| \leq b-a\\\end{array}$

This looks way more complicated than the previous check, but depending on how complex $$a$$ and $$b$$ is, it can shrink down the equation quite a lot. I now was wondring, if we can express $$a<x<b$$ and $$a\leq x \leq b$$ as an absolute value, would it be possible to express a range check with mixed operators the same way? Like $$a<x\leq b$$ and $$a\leq x < b$$. Obviously, this can hold only for $$a,b,x\in\mathbb{Z}$$:

$\begin{array}{rl}& a < x \leq b\\\Leftrightarrow & a < x < b + 1\\\overset{*}{\Leftrightarrow} & |2(x-a)-(b+1-a)| \leq (b+1)-a\end{array}$

Again: The result looks more complicated than the one we started with, but it can be simplified a lot in some cases.

Give me an example

Let's say you want to plot a 11 by 6 pyramid on the console in one rush and only need to decide if a white-space is printed for the current line or a printable character:

for (i = 0; i < 6; i++) {
for (j = 0; j < 11; j++) {
print COND(i, j) ? 'X' : ' '
}
print '\n'
}

You need to formulate a range-check based on the variables $$i$$ and $$j$$. You can argue, that the following checks are needed to print a pyramide:

i: range
0: 4,6
1: 3,7
2: 2,8
3: 1,9
4: 0,10

Which result in the range check: $4-i < j \&\& j < 6+i$

Re-formulating this with the formula we just derived:

$\begin{array}{rl}& |2(j-(4-i))-((6+i)-(4-i))| < ((6+i)-(4-i))\\=& |j-5| < i + 1\\=& |j-5| \leq i\\\end{array}$

Bitwise-OR Trick

When bitwise OR-ing together two natural numbers $$x$$ and $$y$$, all bits set on both numbers will be set on the result as well. The idea now is, when OR-ing the numbers where $$y$$ is of the form $$y:= 2^k-1$$, the result will always be $$2^k-1$$ as long as $$x\leq 2^k-1$$, which means that $$x | (2^k-1) = 2^k - 1\Leftrightarrow a\leq 2^k-1 \forall k\in\mathbb{N}$$.

We can extend this idea to $$x | ((2^j - 1)-(2^i - 1)) = 2^j - 1$$. It turns out that when we get an interval $$[a, b]$$ and $$b+1$$ is a power of two (like 1, 3, 7, 15, ...) as well as $$b-a\geq 0$$ is a power of two, we can rewrite the interval-check to

$x | (b - a) = b$

For example $$12\leq x\leq 15$$ is then $$x | 3 = 15$$.

Draw examples

Height Width Expression

Other Examples:

You might also be interested in the following

Sorry, comments are closed for this article. Contact me if you want to leave a note.