C битная операционная головоломка - PullRequest
Новая
       45

C битная операционная головоломка

5 голосов
/ 08 февраля 2012 
/*
 * 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)

Что не так с этим решением?

Ответы [ 4 ]

2 голосов
/ 08 февраля 2012

Вот что я сделал: 

#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;
}

Вывод: 

      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

Причина, по которой я не использовал сдвиги вправо для отрицательных целых чисел, проста.Результат этих сдвигов определяется реализацией (в соответствии со стандартом C) и не гарантируется, что он будет таким же, как от правого сдвига с расширением знака, которое мы могли ожидать, поскольку оно является наиболее распространенной реализацией.

Я написал (UINT_MAX - x3 + 1) вместо простого -x3, потому что это может привести к переполнению со знаком (когда x3 = INT_MIN, то есть минус степень 2), что ведет к неопределенному поведению (опять же, в соответствии со стандартом C).И даже если известно, что это неопределенное поведение безвредно, простое отрицание все равно может не дать положительного числа (из-за асимметрии в представлении дополнения 2 целыми числами со знаком).

x + x + x может по-прежнему создавать подписанное числопереполнение, как может x * 3.Таким образом, это то же неопределенное поведение.

Кстати, поскольку подписанные переполнения приводят к UB, от вас даже не следует требовать юридически их достигать, не говоря уже о конкретных ожиданиях в отношении результатов при возникновении UB.

1 голос
/ 08 февраля 2012 
int ezThreeFourths(int x) {  


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


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

}

Работает с неотрицательными числами. Также вы не должны лгать о коде «вы», написанном . Учитывая точный код был написан в "2008-01-26"

0 голосов
/ 08 февраля 2012

Ваш подход для округления отрицательных чисел к нулю не работает должным образом в случае входных значений, которые делятся равномерно на 4. 0x80000000 - один из таких примеров, но, возможно, легче увидеть проблему, если вы попробуете с небольшим значением.

Например: ezThreeFourths (-8) = -5 [должно быть -6]

0 голосов
/ 08 февраля 2012

Работает нормально для меня, используя 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
}
...