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

Question

例如，n = 3432, result 4n = 45, result 2n = 33215, result 5n = -357, result 3我想我可以将其转换为字符串，然后获取字符串的长度，但这似乎令人费解且容易理解。

Answer 1

递归方法：-)

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

Answer 2

二进制搜索伪算法，以获取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;