C中的二进制分解

Question

我正在编写一些东西来分解训练网站上的二进制数字.我在我的本地编译器上测试了一百次,它运行得很好,但是训练网站告诉我有错误.

(我的代码既不优雅也不高效,尤其是循环,但我分解了代码以了解错误的位置).有人能告诉我是否有错误吗？

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


//function that displays the greatest power of 2 less than a fixed number N
int residu(int N)

{
    int i;
    int M=2;
    for(i=0;i<N;i++){
        if(M>N){break;}else{M=2*M;i++;}
    }
    return M/2;
}


int main()
{
    int i;

    //N is the input to decompose
    int N;
    scanf("%d",&N);
    //We will search for the greatest power of 2 less than a fixed number N, 
    //than repeating the some process with the residue of N with the greatest power of 2        //less than N, so we have to store the value of N for the loop (see below) we will use to work //correctly
    int M;
    M=N;
    //D displays the diffrence betwenn two successive powers of 2 that appears in the    //binary decomposition, (we will then print "O")
    int D;
    D=log(residu(N))/log(2);

        for(i=0;i<M;i++){
            //If N==residu(N), the decomposition is finished
            if(N==residu(N)){printf("1");int k;
                for(k=0;k<D;k++){printf("0");}break;}
            else{
             // N is a the residue of the former value of N and the greatest power of 2 //less than N
                N=N-residu(N);
                D=D-log(residu(N))/log(2);
                printf("1");
                int k;
                for(k=0;k<D-1;k++){printf("0");
                }
                D=log(residu(N))/log(2);
            }        
    }
}

Answer 1

这是浮点计算的典型问题.该函数log适用于浮点数.

log(8) / log(2)正在计算2.999...,然后2在转换为时被截断为int.

这就是你得到错误结果的原因.确切的行为取决于编译器/机器.如需进一步阅读,请参阅Goldberg.

通过这种方式混合整数和浮点计算通常是个坏主意.您的函数residu应该报告确切的二进制对数.或者你实现了一个专门的函数来计算整数的日志,比如

unsigned binlog(unsigned n) {
    unsigned i = 0;
    while (n > 1) { n /= 2; ++i; }
    return i;
}