如何手动(按位)执行(浮点)x? [英] How to manually (bitwise) perform (float)x?

问题描述

现在，这是我应该实现的函数的函数头:

Now, here is the function header of the function I'm supposed to implement:

/*
 * float_from_int - Return bit-level equivalent of expression (float) x
 *   Result is returned as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point values.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned float_from_int(int x) {
...
}

我们不允许进行浮动操作或任何类型的转换.

We aren't allowed to do float operations, or any kind of casting.

现在我尝试实现本网站给出的第一个算法:http://locklessinc.com/articles/i2f/

Now I tried to implement the first algorithm given at this site: http://locklessinc.com/articles/i2f/

这是我的代码:

unsigned float_from_int(int x) {

// grab sign bit

  int xIsNegative = 0;
  int absValOfX = x;

  if(x < 0){
    xIsNegative = 1;
    absValOfX = -x;
  }




  // zero case
  if(x == 0){
    return 0;
  }
  if(x == 0x80000000){ //Updated to add this
    return 0xcf000000;
  }
  //int shiftsNeeded = 0;

  /*while(){

    shiftsNeeded++;
    }*/


  unsigned I2F_MAX_BITS = 15;
  unsigned I2F_MAX_INPUT = ((1 << I2F_MAX_BITS) - 1);
  unsigned I2F_SHIFT = (24 - I2F_MAX_BITS);

  unsigned result, i, exponent, fraction;

  if ((absValOfX & I2F_MAX_INPUT) == 0)
    result = 0;
  else {
    exponent = 126 + I2F_MAX_BITS;
    fraction = (absValOfX & I2F_MAX_INPUT) << I2F_SHIFT;

    i = 0;
    while(i < I2F_MAX_BITS) {
      if (fraction & 0x800000)
        break;
      else {
        fraction = fraction << 1;
        exponent = exponent - 1;
      }
      i++;
    }
    result = (xIsNegative << 31) | exponent << 23 | (fraction & 0x7fffff);
  }
  return result;
}

但是没有用(见下面的测试错误):

But it didn't work (see test error below):

ERROR: Test float_from_int(8388608[0x800000]) failed...
...Gives 0[0x0]. Should be 1258291200[0x4b000000]

我不知道从哪里开始.我应该如何从这个 int 解析浮点数?

I don't know where to go from here. How should I go about parsing the float from this int?

编辑#1:你可能会从我的代码中看到我也开始研究这个算法(查看本网站):

EDIT #1: You might be able to see from my code that I also started working on this algorithm (see this site):

我假设了 10 位，2 的补码，整数，因为尾数只是9 位，但该过程推广到更多位.

I assumed 10-bit, 2’s complement, integers since the mantissa is only 9 bits, but the process generalizes to more bits.

Save the sign bit of the input and take the absolute value of the input.
Shift the input left until the high order bit is set and count the number of shifts required. This forms the floating mantissa.
Form the floating exponent by subtracting the number of shifts from step 2 from the constant 137 or (0h89-(#of shifts)).
Assemble the float from the sign, mantissa, and exponent.

但是，这似乎不对.我怎么能转换 0x80000000?没有意义.

But, that doesn't seem right. How could I convert 0x80000000? Doesn't make sense.

编辑#2:我想这是因为我说最大位是 15...嗯...

EDIT #2: I think it's because I say max bits is 15... hmmm...

编辑 #3:搞砸那个旧算法，我要重新开始:

EDIT #3: Screw that old algorithm, I'm starting over:

unsigned float_from_int(int x) {

  // grab sign bit

  int xIsNegative = 0;
  int absValOfX = x;

  if(x < 0){
    xIsNegative = 1;
    absValOfX = -x;
  }


  // zero case
  if(x == 0){
    return 0;
  }
  if (x == 0x80000000){
    return 0xcf000000;
  }

  int shiftsNeeded = 0;

  int counter = 0;
  while(((absValOfX >> counter) & 1) != 1 && shiftsNeeded < 32){

    counter++;
    shiftsNeeded++;
  }

  unsigned exponent = shiftsNeeded + 127;

  unsigned result = (xIsNegative << 31) | (exponent << 23);

  return result;

这是我在这个错误上遇到的错误(我想我已经克服了最后一个错误):

Here's the error I get on this one (I think I got past the last error):

ERROR: Test float_from_int(-2139095040[0x80800000]) failed...
...Gives -889192448[0xcb000000]. Should be -822149120[0xceff0000]

了解以下信息可能会有所帮助:absValOfX = 7f800000(使用 printf)

May be helpful to know that: absValOfX = 7f800000 (using printf)

编辑 #4:啊，我发现指数错误，需要从左边数，然后从我相信的 32 中减去.

EDIT #4: Ah, I'm finding the exponent wrong, need to count from the left, then subtract from 32 I believe.

编辑 #5:我重新开始，现在试图处理奇怪的舍入问题......

EDIT #5: I started over, now trying to deal with weird rounding problems...

  if (x == 0){
    return 0; // 0 is a special case because it has no 1 bits
  }
  if (x >= 0x80000000 && x <= 0x80000040){
    return 0xcf000000;
  }
  // Save the sign bit of the input and take the absolute value of the input.
  unsigned signBit = 0;
  unsigned absX = (unsigned)x;
  if (x < 0)
    {
      signBit = 0x80000000u;
      absX = (unsigned)-x;
    }

  // Shift the input left until the high order bit is set to form the mantissa.
  // Form the floating exponent by subtracting the number of shifts from 158.
  unsigned exponent = 158;
  while ((absX & 0x80000000) == 0)
    {
      exponent--;
      absX <<= 1;
    }

  unsigned negativeRoundUp = (absX >> 7) & 1 & (absX >> 8);

  // compute mantissa
  unsigned mantissa = (absX >> 8) + ((negativeRoundUp) || (!signBit & (absX >> 7) & (exponent < 156)));
  printf("absX = %x, absX >> 8 = %x, exponent = %i,  mantissa = %x
", absX, (absX >> 8), exponent, mantissa);
  // Assemble the float from the sign, mantissa, and exponent.
  return signBit | ((exponent << 23) + (signBit & negativeRoundUp)) | ( (mantissa) & 0x7fffff);

-

absX = fe000084, absX >> 8 = fe0000, exponent = 156,  mantissa = fe0000
ERROR: Test float_from_int(1065353249[0x3f800021]) failed...
...Gives 1316880384[0x4e7e0000]. Should be 1316880385[0x4e7e0001]

编辑 #6

又做了一遍，仍然，舍入不能正常工作.我试图将一些四舍五入拼凑起来，但它就是行不通...

Did it again, still, the rounding doesn't work properly. I've tried to hack together some rounding, but it just won't work...

unsigned float_from_int(int x) {






  /*
  If N is negative, negate it in two's complement. Set the high bit (2^31) of the result.
    If N < 2^23, left shift it (multiply by 2) until it is greater or equal to.
    If N ≥ 2^24, right shift it (unsigned divide by 2) until it is less.
    Bitwise AND with ~2^23 (one's complement).
    If it was less, subtract the number of left shifts from 150 (127+23).
  If it was more, add the number of right shifts to 150.
    This new number is the exponent. Left shift it by 23 and add it to the number from step 3.
  */

  printf("---------------
");
  //printf("x = %i (%x), -x = %i, (%x)
", x, x, -x, -x);
  if(x == 0){
    return 0;
  }

  if(x == 0x80000000){
    return 0xcf000000;
  }

  // If N is negative, negate it in two's complement. Set the high bit of the result
  unsigned signBit = 0;

  if (x < 0){
    signBit = 0x80000000;
    x = -x;
  }

  printf("abs val of x = %i (%x)
", x, x);

  int roundTowardsZero = 0;
  int lastDigitLeaving = 0;
  int shiftAmount = 0;
  int originalAbsX = x;

  // If N < 2^23, left shift it (multiply it by 2) until it is great or equal to.
  if(x < (8388608)){
    while(x < (8388608)){
      //printf(" minus shift and x = %i", x );
      x = x << 1;
      shiftAmount--;
    }
  } // If N >= 2^24, right shfit it (unsigned divide by 2) until it is less.
 else if(x >= (16777215)){
    while(x >= (16777215)){

      /*if(x & 1){
        roundTowardsZero = 1;
        printf("zzz Got here ---");
        }*/

      lastDigitLeaving = (x >> 1) & 1;
      //printf(" plus shift and x = %i", x);
      x = x >> 1;
      shiftAmount++;

    }
    //Round towards zero
    x = (x + (lastDigitLeaving && (!(originalAbsX > 16777216) || signBit)));




    printf("x = %i
", x);
    //shiftAmount = shiftAmount + roundTowardsZero;
  }

  printf("roundTowardsZero = %i, shiftAmount = %i (%x)
", roundTowardsZero, shiftAmount, shiftAmount);

  // Bitwise AND with 0x7fffff
 x = x & 0x7fffff;

  unsigned exponent = 150 + shiftAmount;

  unsigned rightPlaceExponent = exponent << 23;

  printf("exponent = %i, rightPlaceExponent = %x
", exponent, rightPlaceExponent);

  unsigned result = signBit | rightPlaceExponent | x;

  return result;

推荐答案

问题是int最低是-2147483648，但最高是2147483647，所以-2147483648没有绝对值.虽然你可以解决它，但我只会为那个一位模式做一个特例(就像你对 0 所做的那样):

The problem is that the lowest int is -2147483648, but the highest is 2147483647, so there is no absolute value of -2147483648. While you could work around it, I would just make a special case for that one bit pattern (like you do for 0):

if (x == 0)
    return 0;
if (x == -2147483648)
    return 0xcf000000;

另一个问题是您复制的算法仅适用于从 0 到 32767 的数字.在文章的后面，他们解释了如何将其扩展到所有整数，但它使用了您可能不允许使用的操作.

The other problem is that you copied an algorithm that only works for numbers from 0 to 32767. Further down in the article they explain how to expand it to all ints, but it uses operations that you're likely not allowed to use.

我建议根据您编辑中提到的算法从头开始编写它.这是 C# 中的一个向 0 舍入的版本:

I would recommend writing it from scratch based on the algorithm mentioned in your edit. Here's a version in C# that rounds towards 0:

uint float_from_int(int x)
{
    if (x == 0)
        return 0; // 0 is a special case because it has no 1 bits

    // Save the sign bit of the input and take the absolute value of the input.
    uint signBit = 0;
    uint absX = (uint)x;
    if (x < 0)
    {
        signBit = 0x80000000u;
        absX = (uint)-x;
    }

    // Shift the input left until the high order bit is set to form the mantissa.
    // Form the floating exponent by subtracting the number of shifts from 158.
    uint exponent = 158;
    while ((absX & 0x80000000) == 0)
    {
        exponent--;
        absX <<= 1;
    }

    // compute mantissa
    uint mantissa = absX >> 8;

    // Assemble the float from the sign, mantissa, and exponent.
    return signBit | (exponent << 23) | (mantissa & 0x7fffff);
}

这篇关于如何手动(按位)执行(浮点)x?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！