In c binary, testing to see if a number is in range

Question

This is part of a puzzle that I can't figure out. The function takes in three inputs. The first is an int, the second is the lower bound and the third is the upper bound. I need to test to see if that first number is within the lower and upper bound inclusive.

If it is in range then return 1, else return 0. The catch is that I can only use

! ~ & ^ | + << >> 

operations and only a combination of 20 of them.. Also, only int variables may be used, and no if statements, loops or function calls.

Range(int x, int lower, int upper){
//... some code here
return retVal;
}

Obviously I understand the logic here. If((x >= lower) && (x <= upper)) return 1; The only problem is that I can't use if statements, <, >, ==, or &&.

Answer 1

You can make the comparison predicate x < y (returning -1 if true, 0 if false) like this: (see Hacker's Delight, Chapter 2, sub-chapter Comparison Predicates)

((x - y) ^ ((x ^ y) & ((x - y) ^ x))) >> 31;

You didn't list subtraction, but you can emulate x - y with ~(~x + y)

Using two of these predicates, make 1 & ~((x < lower) | (upper < x))

This obviously assumes 2's complement negatives and 32 bit integers with wrapping on overflow. So this is not portable, but that's the norm with this kind of trick.

---

As requested, that makes the total thing:

int in_range(int x, int lower, int upper)
{
    int p = ((x - lower) ^ ((x ^ lower) & ((x - lower) ^ x))) >> 31;
    int q = ((upper - x) ^ ((upper ^ x) & ((upper - x) ^ upper))) >> 31;
    return 1 & ~(p | q);
}

It still has the subtractions, they're trivial to replace if you really want.

It's possible to make it a tiny tiny bit shorter by using the >= and <= predicates (which can also be found in Hacker's Delight).

Here's my website saying it's correct.

---

And here's a way that uses less operations, keeping in mind we can't use subtraction:

int p = (x | ~upper) & ((x ^ upper) | (~upper + x));
int q = (lower | ~x) & ((lower ^ x) | (~x + lower));
return 1 & ((p & q) >> 31);

It uses the <= predicate from HD, which looks like (x | ~y) & ((x ^ y) | ~(y - x)) in its pure form.

And here's my website saying it's correct.

Answer 2

Here is a humble solution

int foo(int num, int upp, int low){
        return (~((~(upp + ~num + 1)) ^ (~(num + ~low + 1))) >> 31) & 1;
}

Answer 3

do this. i'll tell the logic that can be used.

a=~x+1    //gives -x
b=lower+a   //lower-x
c=~upper+1    //gives -upper
d=x+c           //x-upper  
b=b&0x80000000;   //get the msb which is 1 if -ve number
d=d&0x80000000;
return ((b&d)|(!(x^lower))|(!(x^upper)));  //& results in +ve only if both b & d are +ve

Answer 4

I'm liking these puzzles you have! For this you will want to have something like,

Ok to be abstract on this one, you will want to have 2 variables.

The first variable (lets call it blarg) you need to set the upper bound and add the flipped x. Now you will want to add one to blarg and flip it.

Your second variable (lets call it hold) will add the x to the flipped lower bound; After that add 1 to hold and flip it too.

set blarg = to the blarg plus hold; shift blarg over 31 to the the right. and AND it with 1.

Should be what you are looking for.