在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'位的位置

回答

相關問題