为了账号安全,请及时绑定邮箱和手机立即绑定

如何确定C中整数的位数?

如何确定C中整数的位数?

森林海 2019-12-17 15:23:27
例如,n = 3432, result 4n = 45, result 2n = 33215, result 5n = -357, result 3我想我可以将其转换为字符串,然后获取字符串的长度,但这似乎令人费解且容易理解。
查看完整描述

3 回答

?
宝慕林4294392

TA贡献2021条经验 获得超8个赞

递归方法:-)


int numPlaces (int n) {

    if (n < 0) return numPlaces ((n == INT_MIN) ? MAX_INT: -n);

    if (n < 10) return 1;

    return 1 + numPlaces (n / 10);

}

或迭代:


int numPlaces (int n) {

    int r = 1;

    if (n < 0) n = (n == INT_MIN) ? INT_MAX: -n;

    while (n > 9) {

        n /= 10;

        r++;

    }

    return r;

}

或原始速度:


int numPlaces (int n) {

    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;

    if (n < 10) return 1;

    if (n < 100) return 2;

    if (n < 1000) return 3;

    if (n < 10000) return 4;

    if (n < 100000) return 5;

    if (n < 1000000) return 6;

    if (n < 10000000) return 7;

    if (n < 100000000) return 8;

    if (n < 1000000000) return 9;

    /*      2147483647 is 2^31-1 - add more ifs as needed

       and adjust this final return as well. */

    return 10;

}

修改了上面的内容,以更好地处理MININT。在任何不遵循明智的2 n二进制补码规则的怪异系统上,可能需要进一步调整。


原始速度版本实际上胜过浮点版本,对其进行了以下修改:


int numPlaces (int n) {

    if (n == 0) return 1;

    return floor (log10 (abs (n))) + 1;

}

经过一亿次迭代,我得到了以下结果:


Raw speed with 0:            0 seconds

Raw speed with 2^31-1:       1 second

Iterative with 2^31-1:       5 seconds

Recursive with 2^31-1:       6 seconds

Floating point with 1:       6 seconds

Floating point with 2^31-1:  7 seconds

这实际上让我有些惊讶-我以为Intel芯片的FPU不错,但我想一般的FP操作仍然无法与手动优化的整数代码竞争。


更新以下Stormsoul的建议:


通过Stormsoul测试乘法迭代解决方案可获得4秒钟的结果,因此尽管它比除法迭代解决方案要快得多,但仍与优化的if语句解决方案不匹配。


从1000个随机生成的数字中选择参数将原始速度时间缩短到2秒,因此,虽然每次都使用相同的参数似乎有些优势,但它仍然是列出的最快方法。


使用-O2进行编译可以提高速度,但不能改善相对位置(我将迭代计数增加了十倍来进行检查)。


任何进一步的分析都必须认真考虑CPU效率的内部工作原理(不同的优化类型,缓存的使用,分支预测,您实际拥有的CPU,房间的环境温度等等),这将妨碍我的付费工作:-)。这是一个有趣的转移,但是在某些时候,优化的投资回报变得太小了而已。我认为我们已经有了足够的解决方案来回答这个问题(毕竟,这与速度无关)。


进一步更新:


这将是我对此答案的最终更新,其中不包含不依赖于体系结构的明显错误。受Stormsoul勇于测量的启发,我发布了我的测试程序(根据Stormsoul自己的测试程序进行了修改)以及此处答案中显示的所有方法的一些示例图。请记住,这是在一台特定的机器上,您的行驶里程可能会因运行位置而异(这就是为什么我发布测试代码的原因)。


随心所欲地处理它:


#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <limits.h>

#include <time.h>


#define numof(a) (sizeof(a) / sizeof(a[0]))


/* Random numbers and accuracy checks. */


static int rndnum[10000];

static int rt[numof(rndnum)];


/* All digit counting functions here. */


static int count_recur (int n) {

    if (n < 0) return count_recur ((n == INT_MIN) ? INT_MAX : -n);

    if (n < 10) return 1;

    return 1 + count_recur (n / 10);

}


static int count_diviter (int n) {

    int r = 1;

    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;

    while (n > 9) {

        n /= 10;

        r++;

    }

    return r;

}


static int count_multiter (int n) {

    unsigned int num = abs(n);

    unsigned int x, i;

    for (x=10, i=1; ; x*=10, i++) {

        if (num < x)

            return i;

        if (x > INT_MAX/10)

            return i+1;

    }

}


static int count_ifs (int n) {

    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;

    if (n < 10) return 1;

    if (n < 100) return 2;

    if (n < 1000) return 3;

    if (n < 10000) return 4;

    if (n < 100000) return 5;

    if (n < 1000000) return 6;

    if (n < 10000000) return 7;

    if (n < 100000000) return 8;

    if (n < 1000000000) return 9;

    /*      2147483647 is 2^31-1 - add more ifs as needed

    and adjust this final return as well. */

    return 10;

}


static int count_revifs (int n) {

    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;

    if (n > 999999999) return 10;

    if (n > 99999999) return 9;

    if (n > 9999999) return 8;

    if (n > 999999) return 7;

    if (n > 99999) return 6;

    if (n > 9999) return 5;

    if (n > 999) return 4;

    if (n > 99) return 3;

    if (n > 9) return 2;

    return 1;

}


static int count_log10 (int n) {

    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;

    if (n == 0) return 1;

    return floor (log10 (n)) + 1;

}


static int count_bchop (int n) {

    int r = 1;

    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;

    if (n >= 100000000) {

        r += 8;

        n /= 100000000;

    }

    if (n >= 10000) {

        r += 4;

        n /= 10000;

    }

    if (n >= 100) {

        r += 2;

        n /= 100;

    }

    if (n >= 10)

        r++;


    return r;

}


/* Structure to control calling of functions. */


typedef struct {

    int (*fnptr)(int);

    char *desc;

} tFn;


static tFn fn[] = {

    NULL,                              NULL,

    count_recur,    "            recursive",

    count_diviter,  "     divide-iterative",

    count_multiter, "   multiply-iterative",

    count_ifs,      "        if-statements",

    count_revifs,   "reverse-if-statements",

    count_log10,    "               log-10",

    count_bchop,    "          binary chop",

};

static clock_t clk[numof (fn)];


int main (int c, char *v[]) {

    int i, j, k, r;

    int s = 1;


    /* Test code:

        printf ("%11d %d\n", INT_MIN, count_recur(INT_MIN));

        for (i = -1000000000; i != 0; i /= 10)

            printf ("%11d %d\n", i, count_recur(i));

        printf ("%11d %d\n", 0, count_recur(0));

        for (i = 1; i != 1000000000; i *= 10)

            printf ("%11d %d\n", i, count_recur(i));

        printf ("%11d %d\n", 1000000000, count_recur(1000000000));

        printf ("%11d %d\n", INT_MAX, count_recur(INT_MAX));

    /* */


    /* Randomize and create random pool of numbers. */


    srand (time (NULL));

    for (j = 0; j < numof (rndnum); j++) {

        rndnum[j] = s * rand();

        s = -s;

    }

    rndnum[0] = INT_MAX;

    rndnum[1] = INT_MIN;


    /* For testing. */

    for (k = 0; k < numof (rndnum); k++) {

        rt[k] = (fn[1].fnptr)(rndnum[k]);

    }


    /* Test each of the functions in turn. */


    clk[0] = clock();

    for (i = 1; i < numof (fn); i++) {

        for (j = 0; j < 10000; j++) {

            for (k = 0; k < numof (rndnum); k++) {

                r = (fn[i].fnptr)(rndnum[k]);

                /* Test code:

                    if (r != rt[k]) {

                        printf ("Mismatch error [%s] %d %d %d %d\n",

                            fn[i].desc, k, rndnum[k], rt[k], r);

                        return 1;

                    }

                /* */

            }

        }

        clk[i] = clock();

    }


    /* Print out results. */


    for (i = 1; i < numof (fn); i++) {

        printf ("Time for %s: %10d\n", fn[i].desc, (int)(clk[i] - clk[i-1]));

    }


    return 0;

}

请记住,您需要确保使用正确的命令行进行编译。特别是,您可能需要明确列出数学库才能开始log10()工作。我在Debian下使用的命令行是gcc -o testprog testprog.c -lm。


而且,就结果而言,这是我的环境的排行榜:


优化级别0:


Time for reverse-if-statements:       1704

Time for         if-statements:       2296

Time for           binary chop:       2515

Time for    multiply-iterative:       5141

Time for      divide-iterative:       7375

Time for             recursive:      10469

Time for                log-10:      26953

优化级别3:


Time for         if-statements:       1047

Time for           binary chop:       1156

Time for reverse-if-statements:       1500

Time for    multiply-iterative:       2937

Time for      divide-iterative:       5391

Time for             recursive:       8875

Time for                log-10:      25438


查看完整回答
反对 回复 2019-12-17
?
蓝山帝景

TA贡献1843条经验 获得超7个赞

二进制搜索伪算法,以获取v。中r的位数。


if (v < 0 ) v=-v;


r=1;


if (v >= 100000000)

{

  r+=8;

  v/=100000000;

}


if (v >= 10000) {

    r+=4;

    v/=10000;

}


if (v >= 100) {

    r+=2;

    v/=100;

}


if( v>=10)

{

    r+=1;

}


return r;


查看完整回答
反对 回复 2019-12-17
  • 3 回答
  • 0 关注
  • 883 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信