C位操作难题

Question

/*
 * 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);
}

我试图解决这个难题但是

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

用gcc编写(GCC)4.1.2 20080704(Red Hat 4.1.2-51)

这个解决方案有什么问题？

Answer 1

使用 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
}