طريقة فعالة لتحديد عدد الأرقام في عدد صحيح
https://stackoverflow.com/questions/1489830
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
ما هو جدا فعال طريقة تحديد عدد الأرقام الموجودة في عدد صحيح في C++؟
المحلول
حسنا، الطريقة الأكثر كفاءة، تفترض أنك تعرف حجم عدد صحيح، ستكون بحثا. يجب أن يكون أسرع من النهج القائم على اللوجريت أقصر. إذا كنت لا تهتم بعد "-"، فقم بإزالة + 1.
// 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 32-bit numbers
template<>
int numDigits(int32_t x)
{
if (x == MIN_INT) 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];
}
نصائح أخرى
أبسط طريقة هي القيام به:
unsigned GetNumberOfDigits (unsigned i)
{
return i > 0 ? (int) log10 ((double) i) + 1 : 1;
}
يتم تعريف log10 في <cmath> أو <math.h>. وبعد كنت بحاجة إلى ملف تعريف هذا لمعرفة ما إذا كان الأمر أسرع من أي من آخرين نشر هنا. لست متأكدا من مدى قوة هذا فيما يتعلق بدقة بوينت تعويم. أيضا، الحجة غير موقعة كقيم سلبية وسجل لا تخلط حقا.
ربما أسيء فهم السؤال ولكن لا يفعل ذلك؟
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)))))))));
}
int digits = 0; while (number != 0) { number /= 10; digits++; }
ملاحظة: "0" سيكون 0 رقما! إذا كنت بحاجة إلى 0 ليظهر أن يكون لديك رقم واحد، استخدم:
int digits = 0; do { number /= 10; digits++; } while (number != 0);
(شكرا كيفن فيان)
في النهاية، استخدم Profiler لمعرفة أي من جميع الإجابات هنا ستكون أسرع على جهازك ...
نكتة عملية: هذا هو ال الطريقة الأكثر كفاءة (يتم احتساب عدد الأرقام في وقت الترجمة):
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 };
};
قد تكون مفيدة لتحديد العرض المطلوب لحقل الرقم بالتنسيق وعناصر الإدخال وما إلى ذلك.
يرى بت التلاعب المأجورون للحصول على نسخة أقصر بكثير من الإجابة التي قبلتها.كما أن لديها ميزة العثور على الإجابة عاجلاً إذا كانت مدخلاتك موزعة بشكل طبيعي، عن طريق التحقق من الثوابت الكبيرة أولاً. (v >= 1000000000) يلتقط 76% من القيم، لذا فإن التحقق من ذلك أولاً سيكون أسرع في المتوسط.
تحويل إلى سلسلة ثم استخدام الوظائف المدمجة
unsigned int i;
cout<< to_string(i).length()<<endl;
اقترح ملصق سابق حلقة تقسم بنسبة 10. نظرا لأن تضاعف الآلات الحديثة أسرع بكثير، أوصي بالتعليمة التالية بدلا من ذلك:
int digits = 1, pten=10; while ( pten <= number ) { digits++; pten*=10; }
بنية PPC لديها تعليمات عد قليلا. مع ذلك، يمكنك تحديد قاعدة السجل 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 خارج اليد، ولكن يجب أن يكون لدى الهندسة الأخرى تعليمات مماثلة.
int x = 1000;
int numberOfDigits = x ? static_cast<int>(log10(abs(x))) + 1 : 1;
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
double num;
int result;
cout<<"Enter a number to find the number of digits, not including decimal places: ";
cin>>num;
result = ((num<=1)? 1 : log10(num)+1);
cout<<"Number of digits "<<result<<endl;
return 0;
}
ربما تكون هذه هي أبسط طريقة لحل مشكلتك، على افتراض أنك تهتم فقط بأرقام قبل العشرية والافتراض على أي شيء أقل من 10 هو رقم واحد فقط.
#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
)
)
);
}
أنا أحب إجابة IRA باكستر. إليك متغير القالب الذي يتعامل مع مختلف الأحجام والصفقات بحد أقصى قيم عدد صحيح (تم تحديثه لرفع الرافعات العليا من الحلقة):
#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_DECHIMAL () للعودة الثوابت لكل نوع على منصاتك. يمكن لمجموعة التحويل البرمجية السحرية بما فيه الكفاية تحسين الدعوة إلى MAX_DECHIMAL () إلى ثابت، ولكن التخصص أفضل مع معظم المجالين اليوم. كما يقف، ربما يكون هذا الإصدار أبطأ لأن تكاليف Max_DeChية أكثر من الاختبارات التي تمت إزالتها من الحلقة.
سأترك كل ذلك بمثابة تمرين للقارئ.
/// 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
)
)
)
);
}
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 وإذا كان هناك معرفة بأنه سيتم تجميع ولكن لا توجد معرفة بمكان أن يكون العنقودية قد يكون تنفيذ شجرة ضبط النفس قد يكون الأفضل
على نحو فعال
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;
}
ومع ذلك، فإن مقتطف رمز آخر، والقيام في الأساس بنفس نفس Vitali ولكن يستخدم البحث الثنائي. يتم تهيئة صفيف القوى كسول مرة واحدة لكل نسخة نوع غير موقعة. التحميل الزائد النوع الموقعة يعتني علامة الطرح.
#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) );
}
إذا كان أي شخص يهتم بالتحسين الإضافي، يرجى ملاحظة أن العنصر الأول من صفيف القوى لا يستخدم أبدا، و l يظهر مع +1 2 مرات.
في حالة عدد الأرقام و هناك حاجة إلى قيمة كل موقف رقمي استخدام هذا:
int64_t = number, digitValue, digits = 0; // or "int" for 32bit
while (number != 0) {
digitValue = number % 10;
digits ++;
number /= 10;
}
digit يمنحك القيمة في عنوان الأرقام التي تتم معالجتها حاليا في الحلقة. على سبيل المثال للعدد 1776 القيمة المكونة هي:
6 في حلقة 1
7 في حلقة 2nd
7 في حلقة 3
1 في الحلقة الرابعة
تحديث 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;
}
يمنع مثيل القالب مع مزدوج، وآخرون. آل.
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;
}
// 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) );
int numberOfDigits(int n){
if(n<=9){
return 1;
}
return 1 + numberOfDigits(n/10);
}
هذا ما سأفعله، إذا كنت تريد ذلك للقاعدة 10. بسرعة كبيرة وأنت لن تحصل على كومة من الكومة شراء أعداد صحيحة العد
int num,dig_quant = 0;
cout<<"\n\n\t\t--Count the digits in Number--\n\n";
cout<<"Enter Number: ";
cin>>num;
for(int i = 1; i<=num; i*=10){
if(num / i > 0){
dig_quant += 1;
}
}
cout<<"\n"<<number<<" include "<<dig_quant<<" digit"
cout<<"\n\nGoodbye...\n\n";
إذا كانت أسرع أكثر كفاءة، فهذا تحسن تحسين أندريه الكسندرسكو. وبعد كان إصداره أسرع بالفعل من الطريقة الساذجة (تقسيم 10 في كل رقم). يعد الإصدار أدناه وقتا ثابتا وأسرع على الأقل على x86-64 وذراعا لجميع الأحجام، ولكنه يحتل مرتين أكبر قدر ممكن من التعليمات البرمجية الثنائية، لذلك ليس كصديقة لذاكرة التخزين المؤقت.
معايير لهذا الإصدار vs الإصدار alexandrescu على بلدي العلاقات العامة على Facebook Copy.
يعمل على unsigned, ، ليس signed.
inline uint32_t digits10(uint64_t v) {
return 1
+ (std::uint32_t)(v>=10)
+ (std::uint32_t)(v>=100)
+ (std::uint32_t)(v>=1000)
+ (std::uint32_t)(v>=10000)
+ (std::uint32_t)(v>=100000)
+ (std::uint32_t)(v>=1000000)
+ (std::uint32_t)(v>=10000000)
+ (std::uint32_t)(v>=100000000)
+ (std::uint32_t)(v>=1000000000)
+ (std::uint32_t)(v>=10000000000ull)
+ (std::uint32_t)(v>=100000000000ull)
+ (std::uint32_t)(v>=1000000000000ull)
+ (std::uint32_t)(v>=10000000000000ull)
+ (std::uint32_t)(v>=100000000000000ull)
+ (std::uint32_t)(v>=1000000000000000ull)
+ (std::uint32_t)(v>=10000000000000000ull)
+ (std::uint32_t)(v>=100000000000000000ull)
+ (std::uint32_t)(v>=1000000000000000000ull)
+ (std::uint32_t)(v>=10000000000000000000ull);
}
بالنسبة لعدد صحيح "X"، فأنت تريد أن تعرف عدد الأرقام، حسنا دون استخدام أي حلقة، يعمل هذا الحل في صيغة واحدة في سطر واحد فقط، لذلك هذا هو الحل الأمثل الذي رأيته في هذه المشكلة.
int x = 1000 ;
cout<<numberOfDigits = 1+floor(log10(x))<<endl ;
هذه هي طريقي للقيام بذلك:
int digitcount(int n)
{
int count = 1;
int temp = n;
while (true)
{
temp /= 10;
if (temp != 0) ++count;
if (temp == 0) break;
}
return count;
}
إليك نهج مختلف:
digits = sprintf(numArr, "%d", num); // where numArr is a char array
if (num < 0)
digits--;
قد لا يكون هذا فعالا، مجرد شيء مختلف عن ما اقترحه الآخرون.
