C++で整数の桁数を決定する非常に効率的な方法は何ですか?
264749 次
32 に答える
117
さて、整数のサイズを知っていると仮定すると、最も効率的な方法はルックアップです。はるかに短い対数ベースのアプローチよりも高速である必要があります。'-'のカウントを気にしない場合は、+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];
}
于 2009-09-28T23:35:57.043 に答える
83
最も簡単な方法は次のとおりです。
unsigned GetNumberOfDigits (unsigned i)
{
return i > 0 ? (int) log10 ((double) i) + 1 : 1;
}
log10 は<cmath>またはで定義されてい<math.h>ます。これをプロファイリングして、ここに投稿された他のものよりも高速かどうかを確認する必要があります。浮動小数点の精度に関して、これがどれほど堅牢かはわかりません。また、負の値とログが実際には混在しないため、引数は符号なしです。
于 2009-09-29T00:00:40.970 に答える
72
おそらく私は質問を誤解しましたが、これはそうではありませんか？
int NumDigits(int x)
{
x = abs(x);
return (x < 10 ? 1 :
(x < 100 ? 2 :
(x < 1000 ? 3 :
(x < 10000 ? 4 :
(x < 100000 ? 5 :
(x < 1000000 ? 6 :
(x < 10000000 ? 7 :
(x < 100000000 ? 8 :
(x < 1000000000 ? 9 :
10)))))))));
}
于 2009-09-30T14:43:06.840 に答える
34
int digits = 0; while (number != 0) { number /= 10; digits++; }
注：「0」は0桁になります。1桁のように表示するために0が必要な場合は、次を使用します。
int digits = 0; do { number /= 10; digits++; } while (number != 0);
（Kevin Feganに感謝します）
最後に、プロファイラーを使用して、ここにあるすべての答えのどれがあなたのマシンでより速くなるかを知ってください...
于 2009-09-28T23:31:42.387 に答える
12
悪ふざけ：これが最も効率的な方法です（桁数はコンパイル時に計算されます）：
template <unsigned long long N, size_t base=10>
struct numberlength
{
enum { value = 1 + numberlength<N/base, base>::value };
};
template <size_t base>
struct numberlength<0, base>
{
enum { value = 0 };
};
書式設定、入力要素などの数値フィールドに必要な幅を決定するのに役立つ場合があります。
于 2009-09-29T01:32:53.983 に答える
9
受け入れた回答のはるかに短いバージョンについては、BitTwiddlingHacksを参照してください。また、最初に大きな定数をチェックすることにより、入力が正規分布している場合に、より早く答えを見つけるという利点もあります。 (v >= 1000000000)値の76％をキャッチするため、最初にチェックする方が平均して高速になります。
于 2009-09-29T05:58:36.433 に答える
9
文字列に変換してから組み込み関数を使用する
unsigned int i;
cout<< to_string(i).length()<<endl;
于 2013-03-24T15:53:48.213 に答える
8
int x = 1000;
int numberOfDigits = x ? static_cast<int>(log10(abs(x))) + 1 : 1;
于 2018-07-04T00:45:18.227 に答える
6
以前のポスターは、10で除算するループを提案しました。最近のマシンでの乗算ははるかに高速であるため、代わりに次のコードをお勧めします。
int digits = 1, pten=10; while ( pten <= number ) { digits++; pten*=10; }
于 2009-09-29T01:05:25.490 に答える
5
ppc アーキテクチャには、ビット カウント命令があります。これにより、1 つの命令で正の整数の底 2 の対数を求めることができます。たとえば、32 ビットは次のようになります。
#define log_2_32_ppc(x) (31-__cntlzw(x))
大きな値でわずかな誤差を処理できる場合は、別のいくつかの命令でそれを対数ベース 10 に変換できます。
#define log_10_estimate_32_ppc(x) (9-(((__cntlzw(x)*1233)+1545)>>12))
これはプラットフォーム固有であり、わずかに不正確ですが、分岐、除算、または浮動小数点への変換も含まれません。すべては必要なものに依存します。
私は ppc 命令しか知りませんが、他のアーキテクチャにも同様の命令があるはずです。
于 2009-09-29T06:30:28.533 に答える
1
アイラ・バクスターの答えが好きです。さまざまなサイズを処理し、最大整数値を処理するテンプレートバリアントを次に示します（ループから上限チェックを引き上げるために更新されました）。
#include <boost/integer_traits.hpp>
template<typename T> T max_decimal()
{
T t = 1;
for (unsigned i = boost::integer_traits<T>::digits10; i; --i)
t *= 10;
return t;
}
template<typename T>
unsigned digits(T v)
{
if (v < 0) v = -v;
if (max_decimal<T>() <= v)
return boost::integer_traits<T>::digits10 + 1;
unsigned digits = 1;
T boundary = 10;
while (boundary <= v) {
boundary *= 10;
++digits;
}
return digits;
}
追加のテストをループから引き上げることで実際にパフォーマンスを向上させるには、max_decimal（）を特殊化して、プラットフォーム上の各タイプの定数を返す必要があります。十分に魔法のコンパイラーは、max_decimal（）の呼び出しを定数に最適化できますが、今日のほとんどのコンパイラーでは、特殊化の方が優れています。現状では、max_decimalはループから削除されたテストよりもコストがかかるため、このバージョンはおそらく低速です。
読者のための演習として、これらすべてを残しておきます。
于 2009-09-29T06:03:47.073 に答える
1
#include <stdint.h> // uint32_t [available since C99]
/// Determine the number of digits for a 32 bit integer.
/// - Uses at most 4 comparisons.
/// - (cX) 2014 adolfo.dimare@gmail.com
/// - \see http://stackoverflow.com/questions/1489830/#27669966
/** #d == Number length vs Number of comparisons == #c
\code
#d | #c #d | #c
---+--- ---+---
10 | 4 5 | 4
9 | 4 4 | 4
8 | 3 3 | 3
7 | 3 2 | 3
6 | 3 1 | 3
\endcode
*/
unsigned NumDigits32bs(uint32_t x) {
return // Num-># Digits->[0-9] 32->bits bs->Binary Search
( x >= 100000u // [6-10] [1-5]
? // [6-10]
( x >= 10000000u // [8-10] [6-7]
? // [8-10]
( x >= 100000000u // [9-10] [8]
? // [9-10]
( x >= 1000000000u // [10] [9]
? 10
: 9
)
: 8
)
: // [6-7]
( x >= 1000000u // [7] [6]
? 7
: 6
)
)
: // [1-5]
( x >= 100u // [3-5] [1-2]
? // [3-5]
( x >= 1000u // [4-5] [3]
? // [4-5]
( x >= 10000u // [5] [4]
? 5
: 4
)
: 3
)
: // [1-2]
( x >= 10u // [2] [1]
? 2
: 1
)
)
);
}
于 2014-12-27T17:59:28.997 に答える
0
// Meta-program to calculate number of digits in (unsigned) 'N'.
template <unsigned long long N, unsigned base=10>
struct numberlength
{ // http://stackoverflow.com/questions/1489830/
enum { value = ( 1<=N && N<base ? 1 : 1+numberlength<N/base, base>::value ) };
};
template <unsigned base>
struct numberlength<0, base>
{
enum { value = 1 };
};
{
assert( (1 == numberlength<0,10>::value) );
}
assert( (1 == numberlength<1,10>::value) );
assert( (1 == numberlength<5,10>::value) );
assert( (1 == numberlength<9,10>::value) );
assert( (4 == numberlength<1000,10>::value) );
assert( (4 == numberlength<5000,10>::value) );
assert( (4 == numberlength<9999,10>::value) );
于 2014-12-21T17:11:55.887 に答える
0
もう 1 つのコード スニペットは、基本的には Vitali のものと同じですが、バイナリ検索を採用しています。Powers 配列は、符号なし型インスタンスごとに 1 回遅延初期化されます。符号付き型のオーバーロードはマイナス記号を処理します。
#include <limits>
#include <type_traits>
#include <array>
template <class T>
size_t NumberOfDecPositions ( T v, typename std::enable_if<std::is_unsigned<T>::value>::type* = 0 )
{
typedef std::array<T,std::numeric_limits<T>::digits10+1> array_type;
static array_type powers_of_10;
if ( powers_of_10.front() == 0 )
{
T n = 1;
for ( T& i: powers_of_10 )
{
i = n;
n *= 10;
}
}
size_t l = 0, r = powers_of_10.size(), p;
while ( l+1 < r )
{
p = (l+r)/2;
if ( powers_of_10[p] <= v )
l = p;
else
r = p;
}
return l + 1;
};
template <class T>
size_t NumberOfDecPositions ( T v, typename std::enable_if<std::is_signed<T>::value>::type* = 0 )
{
typedef typename std::make_unsigned<T>::type unsigned_type;
if ( v < 0 )
return NumberOfDecPositions ( static_cast<unsigned_type>(-v) ) + 1;
else
return NumberOfDecPositions ( static_cast<unsigned_type>(v) );
}
さらなる最適化が必要な場合は、powers 配列の最初の要素は使用されず、が2 回l出現することに注意してください。+1
于 2013-09-16T16:58:29.520 に答える
0
/// Determine the number of digits for a 64 bit integer.
/// - Uses at most 5 comparisons.
/// - (cX) 2014 adolfo.dimare@gmail.com
/// - \see http://stackoverflow.com/questions/1489830/#27670035
/** #d == Number length vs Number of comparisons == #c
\code
#d | #c #d | #c #d | #c #d | #c
---+--- ---+--- ---+--- ---+---
20 | 5 15 | 5 10 | 5 5 | 5
19 | 5 14 | 5 9 | 5 4 | 5
18 | 4 13 | 4 8 | 4 3 | 4
17 | 4 12 | 4 7 | 4 2 | 4
16 | 4 11 | 4 6 | 4 1 | 4
\endcode
*/
unsigned NumDigits64bs(uint64_t x) {
return // Num-># Digits->[0-9] 64->bits bs->Binary Search
( x >= 10000000000ul // [11-20] [1-10]
?
( x >= 1000000000000000ul // [16-20] [11-15]
? // [16-20]
( x >= 100000000000000000ul // [18-20] [16-17]
? // [18-20]
( x >= 1000000000000000000ul // [19-20] [18]
? // [19-20]
( x >= 10000000000000000000ul // [20] [19]
? 20
: 19
)
: 18
)
: // [16-17]
( x >= 10000000000000000ul // [17] [16]
? 17
: 16
)
)
: // [11-15]
( x >= 1000000000000ul // [13-15] [11-12]
? // [13-15]
( x >= 10000000000000ul // [14-15] [13]
? // [14-15]
( x >= 100000000000000ul // [15] [14]
? 15
: 14
)
: 13
)
: // [11-12]
( x >= 100000000000ul // [12] [11]
? 12
: 11
)
)
)
: // [1-10]
( x >= 100000ul // [6-10] [1-5]
? // [6-10]
( x >= 10000000ul // [8-10] [6-7]
? // [8-10]
( x >= 100000000ul // [9-10] [8]
? // [9-10]
( x >= 1000000000ul // [10] [9]
? 10
: 9
)
: 8
)
: // [6-7]
( x >= 1000000ul // [7] [6]
? 7
: 6
)
)
: // [1-5]
( x >= 100ul // [3-5] [1-2]
? // [3-5]
( x >= 1000ul // [4-5] [3]
? // [4-5]
( x >= 10000ul // [5] [4]
? 5
: 4
)
: 3
)
: // [1-2]
( x >= 10ul // [2] [1]
? 2
: 1
)
)
)
);
}
于 2014-12-27T18:06:49.887 に答える
0
推奨ソリューションの C++11 更新:
#include <limits>
#include <type_traits>
template <typename T>
typename std::enable_if<std::numeric_limits<T>::is_integer, unsigned int>::type
numberDigits(T value) {
unsigned int digits = 0;
if (value < 0) digits = 1;
while (value) {
value /= 10;
++digits;
}
return digits;
}
double などによるテンプレートのインスタンス化を防ぎます。アル。
于 2014-11-02T17:52:38.830 に答える
0
整数 'X' の場合、桁数を知りたいのですが、ループを使用しなくても問題ありません。このソリューションは 1 行の 1 つの数式でのみ機能するため、これは私がこれまでに見た中で最も最適なソリューションです。
int x = 1000 ;
cout<<numberOfDigits = 1+floor(log10(x))<<endl ;
于 2017-02-27T21:16:17.313 に答える
0
桁数と各桁位置の値が必要な場合は、これを使用します。
int64_t = number, digitValue, digits = 0; // or "int" for 32bit
while (number != 0) {
digitValue = number % 10;
digits ++;
number /= 10;
}
digit現在ループで処理されている番号位置の値を示します。たとえば、数値 1776 の場合、数字の値は次のとおりです。
1 番目のループでは 6
2 番目のループ
では 7 3 番目のループでは 7
4 番目のループでは 1
于 2014-03-27T15:50:16.030 に答える
-1
効果的な方法
int num;
int count = 0;
while(num)
{
num /= 10;
++count;
}
#include <iostream>
int main()
{
int num;
std::cin >> num;
std::cout << "number of digits for " << num << ": ";
int count = 0;
while(num)
{
num /= 10;
++count;
}
std::cout << count << '\n';
return 0;
}
于 2009-09-30T13:23:29.073 に答える
-1
template <typename type>
class number_of_decimal_digits {
const powers_and_max<type> mPowersAndMax;
public:
number_of_decimal_digits(){
}
inline size_t ndigits( type i) const {
if(i<0){
i += (i == std::numeric_limits<type>::min());
i=-i;
}
const type* begin = &*mPowersAndMax.begin();
const type* end = begin+mPowersAndMax.size();
return 1 + std::lower_bound(begin,end,i) - begin;
}
inline size_t string_ndigits(const type& i) const {
return (i<0) + ndigits(i);
}
inline size_t operator[](const type& i) const {
return string_ndigits(i);
}
};
私たちはどこにそのようなものpowers_and_maxを持って(10^n)-1いますかn
(10^n) < std::numeric_limits<type>::max()
そしてstd::numeric_limits<type>::max()配列で：
template <typename type>
struct powers_and_max : protected std::vector<type>{
typedef std::vector<type> super;
using super::const_iterator;
using super::size;
type& operator[](size_t i)const{return super::operator[](i)};
const_iterator begin()const {return super::begin();}
const_iterator end()const {return super::end();}
powers_and_max() {
const int size = (int)(log10(double(std::numeric_limits<type>::max())));
int j = 0;
type i = 10;
for( ; j<size ;++j){
push_back(i-1);//9,99,999,9999 etc;
i*=10;
}
ASSERT(back()<std::numeric_limits<type>::max());
push_back(std::numeric_limits<type>::max());
}
};
ここに簡単なテストがあります：
number_of_decimal_digits<int> ndd;
ASSERT(ndd[0]==1);
ASSERT(ndd[9]==1);
ASSERT(ndd[10]==2);
ASSERT(ndd[-10]==3);
ASSERT(ndd[-1]==2);
ASSERT(ndd[-9]==2);
ASSERT(ndd[1000000000]==10);
ASSERT(ndd[0x7fffffff]==10);
ASSERT(ndd[-1000000000]==11);
ASSERT(ndd[0x80000000]==11);
もちろん、順序付けられたセットの他の実装が使用される可能性がありpowers_and_max、クラスタリングがあるという知識があったが、クラスタがどこにあるのかという知識がない場合は、おそらく自己調整ツリーの実装が最適かもしれません
于 2009-09-29T06:10:07.003 に答える
-1
int numberOfDigits(double number){
if(number < 0){
number*=-1;
}
int i=0;
while(number > pow(10, i))
i++;
cout << "This number has " << i << " digits" << endl;
return i;
}
于 2014-12-14T21:21:48.627 に答える
-2
これが私のやり方です：
int digitcount(int n)
{
int count = 1;
int temp = n;
while (true)
{
temp /= 10;
if (temp != 0) ++count;
if (temp == 0) break;
}
return count;
}
于 2015-08-01T08:14:55.090 に答える
-4
別のアプローチを次に示します。
digits = sprintf(numArr, "%d", num); // where numArr is a char array
if (num < 0)
digits--;
これは効率的ではない可能性があり、他の人が提案したものとは異なるだけです。
于 2009-09-29T05:32:14.873 に答える