乘以5/8并观察溢出

Question

我真的快要破解这个东西了，但我仍然不知道如何注意这个溢出。

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)

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

编辑

我必须实现向零的舍入。

Answer 1

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

Answer 2

我希望这就是你正在搜索的：

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

想法很简单：

将任何参数转换为正数，并在乘法后将最高有效位掩码为0(这应实现overflow behavior)

• divide

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

Answer 3

我相信这段代码应该涵盖了溢出需求。

请注意，这样的代码在现实世界中是没有意义的。

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