Effizient Anzahl der Stellen in einer ganzen Zahl zu bestimmen,
https://stackoverflow.com/questions/1489830
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Was ist eine sehr effizient Art und Weise zu bestimmen, wie viele Stellen gibt es in einer ganzen Zahl in C ++?
Lösung
Nun, der effizienteste Weg, vorausgesetzt, Sie die Größe der ganzen Zahl wissen, wäre ein Nachschlag sein. Sollte schneller sein als die viel kürzer Logarithmus basierenden Ansatz. Wenn Sie kümmern sich nicht um das Zählen der ‚-‘., Entfernen Sie die + 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];
}
Andere Tipps
Der einfachste Weg ist zu tun:
unsigned GetNumberOfDigits (unsigned i)
{
return i > 0 ? (int) log10 ((double) i) + 1 : 1;
}
log10 in <cmath> oder <math.h> definiert. Sie müssen dies profilieren, um zu sehen, ob es schneller als alle andere hier gepostet. Ich bin mir nicht sicher, wie robust diese hinsichtlich ist punktgenau zu schweben. Auch wird das Argument als negative Werte unsigned und melden Sie sich nicht wirklich mischen.
Vielleicht falsch verstanden habe ich die Frage aber nicht das es nicht?
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++; }
Hinweis: "0" 0 Ziffern haben! Wenn Sie 0 benötigen 1 Stelle zu haben, angezeigt werden soll, verwenden:
int digits = 0; do { number /= 10; digits++; } while (number != 0);
(Danke Kevin Fegan)
Am Ende einen Profiler verwenden, um zu wissen hier, welche von allen Antworten wird schneller auf Ihrem Rechner ...
Ulk: Dies ist die effizienteste Weg (Anzahl der Stellen wird zur Übersetzungszeit berechnet):
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 };
};
nützlich sein, kann die Breite für Nummernfeld in der Formatierung, Eingabeelemente usw. erforderlich, um zu bestimmen.
Siehe Bit Twiddling Hacks für eine viel kürzere Version der Antwort akzeptiert. Es hat auch den Vorteil der Suche nach der Antwort früher, wenn Sie Ihre Eingabe normalerweise verteilt wird, durch die großen Konstanten erste Überprüfung. (v >= 1000000000) fängt 76% der Werte, so überprüft, dass die erste Wille im Durchschnitt schneller sein.
in String konvertieren und dann integrierte Funktionen verwenden
unsigned int i;
cout<< to_string(i).length()<<endl;
A vorheriges Plakat vorgeschlagen, eine Schleife, die durch 10 teilt. Da vervielfacht auf modernen Maschinen viel schneller sind, würde ich den folgenden Code empfehlen stattdessen:
int digits = 1, pten=10; while ( pten <= number ) { digits++; pten*=10; }
Die ppc Architektur hat ein bisschen das Zählen Anweisung. Damit können Sie die Log-Basis 2 für eine positive ganze Zahl in einem einzigen Befehl bestimmen. Zum Beispiel würde 32 Bit sein:
#define log_2_32_ppc(x) (31-__cntlzw(x))
Wenn Sie eine kleine Fehlermarge umgehen kann auf große Werte, die Sie, dass konvertieren Basis 10 mit noch ein paar Anweisungen zu protokollieren:
#define log_10_estimate_32_ppc(x) (9-(((__cntlzw(x)*1233)+1545)>>12))
Dies ist plattformspezifisch und etwas ungenau, sondern beinhaltet auch keine Zweige, Spaltung oder Umwandlung in Fließkomma. Alles hängt davon ab, was Sie brauchen.
Ich kenne nur die ppc Anweisungen aus der Hand, aber auch andere Architekturen sollten ähnliche Anweisungen haben.
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;
}
Dies ist wahrscheinlich der einfachste Weg, um Ihr Problem zu lösen, unter der Annahme, nur Sie Ziffern vor dem Komma kümmern und unter der Annahme, etwas weniger als 10 ist nur 1 Stelle.
#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
)
)
);
}
Ich mag Ira Baxter Antwort. Hier ist eine Vorlage Variante, die die verschiedenen Größen und beschäftigt sich mit den maximalen ganzzahligen Werten (aktualisiert, um die obere Schranke Kontrolle aus der Schleife hissen) behandelt:
#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;
}
Um tatsächlich die verbesserte Leistung erhalten vom Hissen des zusätzlichen Tests aus der Schleife, müssen Sie max_decimal () spezialisieren Konstanten auf Ihrer Plattform für jede Art zurückzukehren. Eine ausreichend Magie Compiler kann den Anruf optimieren () auf eine Konstante max_decimal, aber Spezialisierung ist besser mit dem meisten Compilern heute. Wie es aussieht, ist diese Version wahrscheinlich langsamer, weil max_decimal mehr als die Tests aus der Schleife entfernt Kosten.
Ich werde alles, was als eine Übung für den Leser überlassen.
/// 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);
}
};
wo in powers_and_max haben wir für alle (10^n)-1 so n dass
(10^n) < std::numeric_limits<type>::max()
und std::numeric_limits<type>::max() in einem Array:
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());
}
};
hier ist ein einfacher Test:
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);
Natürlich kann jede andere Implementierung eines geordneten Satzes könnte für powers_and_max verwendet werden, und wenn es das Wissen dort Clustering sein würde, aber keine Kenntnis davon, wo der Cluster sein könnte vielleicht eine selbstnachstellende Baum-Implementierung könnte am besten sein,
effektive Art und Weise
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;
}
Noch ein anderer Code-Schnipsel, tut im Grunde die gleichen wie Vitali aber beschäftigt binäre Suche. Powers Array wird lazy initialisiert einmal pro unsigned Typ-Instanz. Signed Art Überlastung nimmt Minuszeichen.
#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) );
}
Wenn jemand von einem weiteren Optimierung kümmert, bitte beachten Sie, dass das erste Element der Kräfte Array wird nie verwendet, und die l erscheint mit +1 2 mal.
, falls die Anzahl der Ziffern der Wert jeder Ziffer Position benötigt wird, um die Verwendung dieses:
int64_t = number, digitValue, digits = 0; // or "int" for 32bit
while (number != 0) {
digitValue = number % 10;
digits ++;
number /= 10;
}
digit gibt Ihnen den Wert an der Zahl Postition, die derzeit in der Schleife verarbeitet wird. zum Beispiel für die Nummer 1776 ist der Zahlenwert:
6 in der ersten Schleife
7 in der zweiten Schleife
7 in der dritten Schleife
1 in der vierten Schleife
C ++ 11-Update von bevorzugter Lösung:
#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;
}
verhindert Vorlage Instanziierung mit Doppel, et. al.
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);
}
Das ist, was ich tun würde, wenn Sie es für Basis 10.Its ziemlich schnell wollen, und Sie prolly nicht einen Stapel erhalten overflock Zählen Zahlen kaufen
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";
Wenn schneller effizienter ist, ist dies eine Verbesserung auf Andrei Alexandrescu die Verbesserung . Seine Version war schon schneller als die naive Art und Weise (Division durch 10 an jeder Stelle). Die Version ist unten konstante Zeit und schneller mindestens auf x86-64 und ARM für alle Größen, sondern nimmt doppelt so viel binären Code, so dass es nicht als Cache freundlich.
istBenchmarks für diese Version vs Alexandrescu-Version auf meinem PR auf Facebook Torheit .
Arbeiten auf unsigned, nicht 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);
}
für integer ‚X‘ können Sie die Anzahl der Stellen, in Ordnung ohne Verwendung einer Schleife, diese Lösung Akt in einer Formel in einer Linie wissen wollen, nur so ist dies die optimale Lösung, die ich je für dieses Problem gesehen habe.
int x = 1000 ;
cout<<numberOfDigits = 1+floor(log10(x))<<endl ;
Das ist mein Weg, das zu tun:
int digitcount(int n)
{
int count = 1;
int temp = n;
while (true)
{
temp /= 10;
if (temp != 0) ++count;
if (temp == 0) break;
}
return count;
}
Hier ist ein anderer Ansatz:
digits = sprintf(numArr, "%d", num); // where numArr is a char array
if (num < 0)
digits--;
Das kann nicht effizient sein, nur etwas anderes als das, was andere vorgeschlagen.
