Robert Eisele
Engineer, Systems Architect and DBA

# 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

### 31 Comments on „Improving Interval Conditions”

Getting A Loan

online loans for bad credit loans payday loans bad credit small payday loan

Quick Loan

Loans Online

loans denver payday loans loans payday loans bad credit

Paydayloan

Loans

Best Payday Loan

Speedycash

Payday Loan Online

Loans Online

loans bad credit payday loans fast loans no credit check loans

Pay Day Loans

loans with bad credit loans easy loans no credit loan for bad credit

Best Payday Loan

Payday

Direct Lender Loans

loan for bad credit easy installment loans online online installment loans direct lenders check city payday loans

Online Payday Loan

payday loans surrey bc loans loans no employment verification payday loan

Loan Cash

Speedy Cash

online loans for bad credit loans for bad credit loans apply online

Direct Lenders

payday loan application loans payday loans bad credit loans

Pay Day Loan

Personal Loans

payday loans bad credit a loan with bad credit need a loan with bad credit payday loan providers

Online Loans

Instant Online Loans

Cash Loan

get a loan with bad credit small payday loan online loans for bad credit bad credit payday loans

Speedycash

tribal loans guaranteed approval payday loan near me loan with bad credit loans

Speedycash

Online Payday Loans

payday loans surrey bc personal loans unsecured loans loans

Best Payday Loan

Quick Loan

loans loans loans bad credit loans guaranteed

Paydayloan