Here's what I did:
#include <stdio.h>
#include <limits.h>
int ThreeFourths(int x)
{
int x3 = x + x + x;
return (x3 >= 0) ? (x3 >> 2) : -(int)((UINT_MAX - x3 + 1) >> 2);
}
int testData[] =
{
0,
1,
-1,
2,
-2,
3,
-3,
4,
-4,
5,
-5,
-9,
11,
INT_MAX / 2 + 1,
INT_MIN
};
int main(void)
{
int i;
for (i = 0; i < sizeof(testData)/sizeof(testData[0]); i++)
{
printf(" %d * 3 / 4 = %d\n",
testData[i], testData[i] * 3 / 4);
printf("ThreeFourths(%d) = %d\n",
testData[i], ThreeFourths(testData[i]));
}
return 0;
}
Output:
0 * 3 / 4 = 0
ThreeFourths(0) = 0
1 * 3 / 4 = 0
ThreeFourths(1) = 0
-1 * 3 / 4 = 0
ThreeFourths(-1) = 0
2 * 3 / 4 = 1
ThreeFourths(2) = 1
-2 * 3 / 4 = -1
ThreeFourths(-2) = -1
3 * 3 / 4 = 2
ThreeFourths(3) = 2
-3 * 3 / 4 = -2
ThreeFourths(-3) = -2
4 * 3 / 4 = 3
ThreeFourths(4) = 3
-4 * 3 / 4 = -3
ThreeFourths(-4) = -3
5 * 3 / 4 = 3
ThreeFourths(5) = 3
-5 * 3 / 4 = -3
ThreeFourths(-5) = -3
-9 * 3 / 4 = -6
ThreeFourths(-9) = -6
11 * 3 / 4 = 8
ThreeFourths(11) = 8
1073741824 * 3 / 4 = -268435456
ThreeFourths(1073741824) = -268435456
-2147483648 * 3 / 4 = -536870912
ThreeFourths(-2147483648) = -536870912
The reason why I didn't use right shifts on negative integers is simple. The result of these shifts is implementation-defined (per the C standard) and is not guaranteed to be the same as from a right shift with sign extension that we might be expecting because of it being the most common implementation.
I wrote (UINT_MAX - x3 + 1)
instead of simply -x3
because it can result a signed overflow (when x3
= INT_MIN
that is a minus power of 2), which has undefined behavior (per the C standard, again). And even if this undefined behavior is known to be harmless, simple negation could still fail to produce a positive number (because of the asymmetry in the 2's complement representation of signed integers).
x + x + x
can still produce signed overflow just as x * 3
can. So, this is the same undefined behavior.
Btw, since signed overflows result in UB, it should not even be legally asked from you to achieve them, let alone have specific expectations about the results when UB occurs.