5
/*
 * ezThreeFourths - multiplies by 3/4 rounding toward 0,
 *   Should exactly duplicate effect of C expression (x*3/4),
 *   including overflow behavior.
 *   Examples: ezThreeFourths(11) = 8
 *             ezThreeFourths(-9) = -6
 *             ezThreeFourths(1073741824) = -268435456 (overflow)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 3
 */

int ezThreeFourths(int x) {
   int z = x+x+x;
   int sign_z = z>>31;
   return ((z>>2)&(~sign_z)) + (((z>>2)+1)&sign_z);
}

I tried to solve this puzzle but


ERROR: Test ezThreeFourths(-2147483648[0x80000000]) failed...
...Gives -536870911[0xe0000001]. Should be -536870912[0xe0000000]

compiled with gcc (GCC) 4.1.2 20080704 (Red Hat 4.1.2-51)

What's wrong with this solution?

5
  • 1
    Hm ... I ran a test with this code in my pc and I have to say it seems to be working for the test cases and the examples you gave here. I even get correct result for 2147483647
    – Lefteris
    Commented Feb 8, 2012 at 2:58
  • Which compiler are you using? Commented Feb 8, 2012 at 3:02
  • 2
    Did you break it down to see all the intermediate values?
    – EboMike
    Commented Feb 8, 2012 at 3:04
  • I forgot to mention which compiler I run the tests with too. It was GCC 4.4.1 under Windows
    – Lefteris
    Commented Feb 8, 2012 at 3:04
  • compiled with gcc (GCC) 4.1.2 20080704 (Red Hat 4.1.2-51) Commented Feb 8, 2012 at 3:05

4 Answers 4

2

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.

1
int ezThreeFourths(int x) {  


  int z = x+x+x;  
  int sign_z = z>>31;  


  return ((z>>2)&(~sign_z)) + (((z>>2)+1)&sign_z);  

}  

Works with non-negative numbers. Also you shouldn't lie about code "you" wrote. Considering the exact code was written in "2008-01-26"

0

Works fine for me using Embarcadero C++ 6.43:

// x = 2147483647
int ezThreeFourths(int x)
{
    int z = x+x+x;
    // z = 2147483645 (6442450941[0x17FFFFFFD] truncated to 32-bits!)

    int sign_z = z>>31;
    // sign_z = (2147483645 >> 31) = 0

    return ((z>>2)&(~sign_z)) + (((z>>2)+1)&sign_z);
    // = ((2147483645 >> 2) & (~0)) + (((2147483645 >> 2) + 1) & 0)
    // = (536870911 & 0xFFFFFFFF) + ((536870911+1) & 0)
    // = (536870911 & 0xFFFFFFFF) + (536870912 & 0)
    // = (536870911 & 0xFFFFFFFF) + 0
    // = (536870911 & 0xFFFFFFFF)
    // = 536870911
}
0

Your approach for making negative numbers round towards zero is not working correctly in the case of input values that divide evenly by 4. 0x80000000 is one such example, but it's perhaps easier to see the problem if you try with a small value.

For example: ezThreeFourths(-8) = -5 [ should be -6 ]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.