1. ホーム
  2. c++

[解決済み] 整数の桁数を効率的に求める方法

2022-04-26 09:40:38

質問

とは何ですか? 効率的 C++で整数の桁数を決定する方法は?

どのように解決するのですか?

最も効率的な方法は、整数のサイズがわかっているのであれば、ルックアップすることです。 対数ベースのアプローチよりずっと速いはずです。 もし、「-」のカウントを気にしないのであれば、「+1」を削除してください。

#include <climits>

// generic solution
template <class T>
int numDigits(T number)
{
    int digits = 0;
    if (number < 0) digits = 1; // remove this line if '-' counts as a digit
    while (number) {
        number /= 10;
        digits++;
    }
    return digits;
}

// partial specialization optimization for 64-bit numbers
template <>
int numDigits(int64_t x) {
    if (x == INT64_MIN) return 19 + 1;
    if (x < 0) return digits(-x) + 1;

    if (x >= 10000000000) {
        if (x >= 100000000000000) {
            if (x >= 10000000000000000) {
                if (x >= 100000000000000000) {
                    if (x >= 1000000000000000000)
                        return 19;
                    return 18;
                }
                return 17;
            }
            if (x >= 1000000000000000)
                return 16;
            return 15;
        } 
        if (x >= 1000000000000) {
            if (x >= 10000000000000)
                return 14;
            return 13;
        }
        if (x >= 100000000000)
            return 12;
        return 11;
    }
    if (x >= 100000) {
        if (x >= 10000000) {
            if (x >= 100000000) {
                if (x >= 1000000000)
                    return 10;
                return 9;
            }
            return 8;
        }
        if (x >= 1000000)
            return 7;
        return 6;
    }
    if (x >= 100) {
        if (x >= 1000) {
            if (x >= 10000)
                return 5;
            return 4;
        }
        return 3;
    }
    if (x >= 10)
        return 2;
    return 1;
}

// partial specialization optimization for 32-bit numbers
template<>
int numDigits(int32_t x)
{
    if (x == INT32_MIN) return 10 + 1;
    if (x < 0) return numDigits(-x) + 1;

    if (x >= 10000) {
        if (x >= 10000000) {
            if (x >= 100000000) {
                if (x >= 1000000000)
                    return 10;
                return 9;
            }
            return 8;
        }
        if (x >= 100000) {
            if (x >= 1000000)
                return 7;
            return 6;
        }
        return 5;
    }
    if (x >= 100) {
        if (x >= 1000)
            return 4;
        return 3;
    }
    if (x >= 10)
        return 2;
    return 1;
}

// partial-specialization optimization for 8-bit numbers
template <>
int numDigits(char n)
{
    // if you have the time, replace this with a static initialization to avoid
    // the initial overhead & unnecessary branch
    static char x[256] = {0};
    if (x[0] == 0) {
        for (char c = 1; c != 0; c++)
            x[c] = numDigits((int32_t)c);
        x[0] = 1;
    }
    return x[n];
}