在C float的base-2表示中获取'ones'位的位置

说我有一个浮点数。我想提取数字的基数2表示中所有数字的位置。例如，10.25 = 2^-2 + 2^1 + 2^3，因此其基数为2的位置是{-2,1,3}。在C float的base-2表示中获取'ones'位的位置

一旦我有一个数字为n的基2次幂的列表，下面应该总是返回true（伪代码）。

sum = 0 
for power in powers: 
    sum += 2.0 ** power 
return n == sum

但是，在C和C++中执行浮点数的位逻辑有点困难，而且更难以移植。

如何使用少量的CPU指令以任何一种语言实现它？

来源

2012-08-03 Vortico

由于该标准不能保证IEEE浮点，因此这种方法不太可能是可移植的。另外，如果“ones”数字超出范围呢？ – Mysticial 2012-08-03 21:40:09

实际上，我不介意非可移植性，只要它可以工作，比如Linux x86_64，带有gcc和有保证的IEEE浮点。任何其他体系结构都可以使用微调代码或慢天真的方法。 – Vortico 2012-08-03 21:43:04

避免低级别，按位操作的要点是什么？ – Nino 2012-08-03 21:43:30

放弃可移植性，假定IEEE float和32位int。

// Doesn't check for NaN or denormalized. 
// Left as an exercise for the reader. 
void pbits(float x) 
{ 
    union { 
     float f; 
     unsigned i; 
    } u; 
    int sign, mantissa, exponent, i; 
    u.f = x; 
    sign = u.i >> 31; 
    exponent = ((u.i >> 23) & 255) - 127; 
    mantissa = (u.i & ((1 << 23) - 1)) | (1 << 23); 
    for (i = 0; i < 24; ++i) { 
     if (mantissa & (1 << (23 - i))) 
      printf("2^%d\n", exponent - i); 
    } 
}

这将打印出总计给定浮点数的两个幂。例如，

 
$ ./a.out 156 
2^7 
2^4 
2^3 
2^2 
$ ./a.out 0.3333333333333333333333333 
2^-2 
2^-4 
2^-6 
2^-8 
2^-10 
2^-12 
2^-14 
2^-16 
2^-18 
2^-20 
2^-22 
2^-24 
2^-25

你可以看到1/3是如何围捕，因为我们总是一轮下来十进制，无论有多少位小数，我们使用的是不直观。

脚注：不要做到以下几点：

float x = ...; 
unsigned i = *(unsigned *) &x; // no

诀窍与union是不太可能产生警告或混淆编译器。

来源

2012-08-03 21:50:39

在代码的顶部，你会看到一条评论'//留给读者作为练习＃ – 2012-08-03 22:28:28

哦，呃，我没有:( – 2012-08-03 22:36:49

这个工程很棒，它也可以有点泛化一堆定义和一对typedefs。谢谢！ – Vortico 2012-08-04 01:21:08

没有必要使用浮点数编码。 C提供了以便携方式处理浮点值的例程。以下作品。

#include <math.h> 
#include <stdio.h> 
#include <stdlib.h> 


int main(int argc, char *argv[]) 
{ 
    /* This should be replaced with proper allocation for the floating-point 
     type. 
    */ 
    int powers[53]; 
    double x = atof(argv[1]); 

    if (x <= 0) 
    { 
     fprintf(stderr, "Error, input must be positive.\n"); 
     return 1; 
    } 

    // Find value of highest bit. 
    int e; 
    double f = frexp(x, &e) - .5; 
    powers[0] = --e; 
    int p = 1; 

    // Find remaining bits. 
    for (; 0 != f; --e) 
    { 
     printf("e = %d, f = %g.\n", e, f); 
     if (.5 <= f) 
     { 
      powers[p++] = e; 
      f -= .5; 
     } 
     f *= 2; 
    } 

    // Display. 
    printf("%.19g =", x); 
    for (int i = 0; i < p; ++i) 
     printf(" + 2**%d", powers[i]); 
    printf(".\n"); 

    // Test. 
    double y = 0; 
    for (int i = 0; i < p; ++i) 
     y += ldexp(1, powers[i]); 

    if (x == y) 
     printf("Reconstructed number equals original.\n"); 
    else 
     printf("Reconstructed number is %.19g, but original is %.19g.\n", y, x); 

    return 0; 
}

来源

2012-08-04 01:39:40

在C float的base-2表示中获取'ones'位的位置

回答

相关问题