0

我真的很接近最终打破这个东西，但我仍然不知道如何注意这个溢出。

int multFiveEighths(int x) {

    int y=((x<<2)+x);
    int f=((y>>3)+1);
    int z=(y>>3);



    return f + ((~!(x>>31&1)+1) & (z+~f+1));

我乘以 5/8，并使用条件位表示：如果符号位为 1（数字为负数），则使用 f，否则使用 z。

其中一部分是包括像 C 表达式 (x*5/8) 这样的溢出行为

那么如何包含溢出行为呢？我只能使用这些操作：！~ & ^ | + << >> 没有循环，没有强制转换，没有函数声明。我离得太近了，这很痛苦。

编辑

我必须实现向零舍入。

4

4 回答 4

2 
int x = num >> 3; // divide by 8 (only defined for positive values)

x = x << 2 + x;   // multiply by 5; no overflow yet since 5/8 is less than one

int y = num & 7;  // the bits we shifted out

y = y << 2 + y;   // multiply by 5; no overflow

return (x + (y >> 3)); // the two pieces

附录，向零舍入为负数：

int s = -((num >> 31) & 1); // sign bit as -1 or 0

int n = (num ^ s) - s; // twos complement if negative

int x = n >> 3; // divide by 8

x = (x << 2) + x;   // multiply by 5; no overflow yet since 5/8 is less than one

int y = n & 7;  // the bits we shifted out

y = (y << 2) + y;   // multiply by 5; no overflow

return (s ^ (x + (y >> 3))) - s; // the two pieces and complemented back
于 2012-09-26T19:51:58.927 回答
1

我希望这是您正在寻找的内容：

int multFiveEights(int x) {

  int isneg = (x>>31);

  // Negative x
  int nx = -x;

  int value = ( (~!!(isneg)+1) &  nx ) + ( (~!(isneg)+1) & x );

  /* Now its positive */
  value = (value<<2) + value;
  value = value & ((-1)>>1); // This mask should produce the desired overflow behavior
  value = (value>>3);

  value = ( (~!!(isneg)+1) & (-value)) + ( (~!(isneg)+1) & (value));

  return value;
}

这个想法很简单：

  1. 将参数转换为正数
  2. 在乘法之后将最高有效位掩码为 0（这应该实现溢出行为）
  3. 划分
  4. 恢复正确的符号

当然，如果您超过了最小数量，您将从 -1 开始。顺便说一句，我可以随意使用-运算符，因为它的行为可以使用您允许的运算符来实现，但我发现它更易于阅读。

于 2012-09-26T20:35:01.527 回答
0

我相信这个片段应该涵盖溢出要求。

请注意，这样的代码在现实世界中没有任何用途。

#include <stdint.h>

uint32_t mult_five_eights (uint32_t num)
{
  num = (num << 2) + num; // multiply by 5
  return num >> 3;        // divide by 8
}

编辑

带有溢出说明的演示程序。它从最大可能的 int 以下开始，然后继续超过溢出。请注意，整数溢出仅对无符号整数进行了明确定义。

#include <stdint.h>
#include <limits.h>
#include <stdio.h>

uint32_t mult_five_eights (uint32_t num)
{
  num = (num << 2) + num; // multiply by 5
  return num >> 3;        // divide by 8
}


int main()
{
  uint32_t i;

  for(i=UINT_MAX/5-10; i<UINT_MAX/5+10; i++)
  {
    uint32_t x = i*5/8;
    uint32_t y = mult_five_eights(i);

    printf("%u %u %u ", i, x, y);

    if(x != y)
    {
      printf("error this should never happen");
    }
    printf("\n");

  }

  return 0;
}
于 2012-09-26T19:34:10.170 回答
0 
int five_eights(int val)
{
int ret, car;

car = ((val&7)+((val&1) <<2)) & 5;
car = (car | (car >>2)) &1;

ret = ((val+1) >>1) + ((val+4) >>3) ;

return ret-car;
}

显然，以上可以进一步压缩/减少；额外的变量是为了清楚起见。

请注意，避免了左移，因此不可能溢出。

于 2012-09-26T20:18:49.250 回答