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