Team. Coco Team. Coco - 4 years ago 102
C Question

Finding if a value falls within a range, using bitwise operators in C

So i am working on this method, but am restricted to using ONLY these operators:

<<, >>, !, ~, &, ^, |, +

I need to find if a given int parameter can be represented using 2's complement arithmetic in a given amount of bits.

Here is what I have so far:

int validRange(int val, int bits){
int minInRange = ~(1<<(bits + ~0 ))+1; //the smallest 2's comp value possible with this many bits
int maxInRange = (1<<(bits+~0))+~0; //largest 2's comp value possible

This is what I have so far, and all I need to do now is figure out how to tell if minInRange <= val <=maxInRange. I wish I could use the greater than or less than operator, but we are not allowed. What is the bitwise way to check this?

Thanks for any help!

Answer Source

Two's complement negative numbers always have a '1' in their high bit.

You can convert from negative to positive (and vice versa) by converting from FF -> 00 -> 01. That is, invert the bits, add 1. (01 -> FE -> FF also works: invert the bits, add 1)

A positive number can be represented if the highest set bit in the number is within your range. (nbits - 1: 7 bits for an 8 bit signed char, etc.)

I'm not sure if your constraints allow you to use arrays. They would speed up some things but can be replaced with loops or if statements.

Anyway, if 1 << (NUM_INT_BITS-1) is set on your input, then it's negative. Invert, add one.

Now, consider 0. Zero is a constant, and it's always the same no matter how many bits. But if you invert 0, you get "all the bits" which changes by architecture. So, ALL_BITS = ~0.

If you want to know if a positive number can be represented in 2 bits, check to see if any bits greater than or equal to bit 2 are set. Example:

two_bits = 0b00000011
any_other_bits = ~two_bits # Result: 0b11...11100
if positive_number & any_other_bits
    this number is too fat for these bits!

But how do you know what ~two_bits should be? Well, it's "all set bits except the bottom however-many". And you can construct that by starting with "all set bits" and shifting them upwards (aka, "left") however-many places:

any_other_bits = ~0 << 2  # where "2" is the number of bits to check

All together now:

if (val & ((unsigned)INT_MAX + 1))
    val = ~val + 1;

mask = ~0 << bits;
too_wide = val & mask;
return !too_wide;
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download