C - Saturating Signed Integer Multiplication with Bitwise Operators

Question

Alright, so the assignment I have to do is to multiply a signed integer by 2 and return the value. If the value overflows then saturate it by returning Tmin or Tmax instead. The challenge is using only these logical operators (! ~ & ^ | + << >>) with no (if statements, loops, etc.) and only allowed a maximum of 20 logical operators.

Now my thought process to tackle this problem was first to find the limits. So I divided Tmin/max by 2 to get the boundaries. Here's what I have:

Positive

This and higher works:

1100000...

This and lower doesn't:

1011111...

If it doesn't work I need to return this:

100000...

Negative

This and lower works:

0011111...

This and higher doesn't:

0100000...

If it doesn't work I need to return this:

011111...

Otherwise I have to return:

2 * x;

(the integers are 32-bit by the way)

I see that the first two bits are important in determining whether or not the problem should return 2*x or the limits. For example an XOR would do since if the first to bits are the same then 2*x should be returned otherwise the limits should be returned. Another if statement is then needed for the sign of the integer for it is negative Tmin needs to be returned, otherwise Tmax needs to be.

Now my question is, how do you do this without using if statements? xD Or a better question is the way I am planning this out going to work or even feasible under the constraints? Or even better question is whether there is an easier way to solve this, and if so how? Any help would be greatly appreciated!

Choanocyte

The CPU is capable of it, by performing a wide multiplication and cmoving the saturation value into the result if the high bits are nonzero. But as for C, it's doubtful to me, and it would still be slower than a library that simply does the above. – Elaterid

Answer 1

a = (x>>31); // fills the integer with the sign bit 
b = (x<<1) >> 31; // fills the integer with the MSB 
x <<= 1; // multiplies by 2
x ^= (a^b)&(x^b^0x80000000); // saturate

So how does this work. The first two lines use the arithmetic right shift to fill the whole integer with a selected bit.

The last line is basically the "if statement". If a==b then the right hand side evaluates to 0 and none of the bits in x are flipped. Otherwise it must be the case that a==~b and the right hand side evaluates to x^b^0x80000000. After the statement is applied x will equal x^x^b^0x80000000 => b^0x80000000 which is exactly the saturation value.

Edit:

Here is it in the context of an actual program.

#include<stdio.h>
main(){
    int i = 0xFFFF;
    while(i<<=1){
        int a = i >> 31;
        int b = (i << 1) >> 31;
        int x = i << 1;
        x ^= (a^b) & (x ^ b ^ 0x80000000);
        printf("%d, %d\n", i, x);
    }
}

Burgess

Haha, I was trying my way originally and was trying to find a way to do the if statement but you've seemed to managed to make it real simple and with a good explanation. This was one of the harder problems that I had to do that I was stuck on for a while so I wanna thank you again for the explanation and all! – Choanocyte

Answer 2

You have a very good starting point. One possible solution is to look at the first two bits.

abxx xxxx

Multiplication by 2 is equivalent to a left shift. So our result would be

bxxx xxx0

We see if b = 1 then we have to apply our special logic. The result in such a case would be

accc cccc

where c = ~a. Thus if we started with bitmasks

m1 = 0bbb bbbb
m2 = b000 0000
m3 = aaaa aaaa & bbbb bbbb

then when b = 1,

x << 1;  // gives 1xxx xxxx
x |= m1; // gives 1111 1111
x ^= m2; // gives 0111 1111
x ^= m3; // gives accc cccc (flips bits for initially negative values)

Clearly when b = 0 none of our special logic happens. It's straightforward to get these bitmasks in just a few operations. Disclaimer: I haven't tested this.

Latchet