Что такое очень эффективный эффективный способ определения количества цифр в целых числах в С++?
Эффективный способ определения числа цифр в целых числах
Ответ 1
Хорошо, самый эффективный способ, предполагающий, что вы знаете размер целого, будет поиском. Должен быть быстрее, чем гораздо более короткий подход на основе логарифма. Если вам не нужно подсчитывать "-", удалите + 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];
}
Ответ 2
Самый простой способ:
unsigned GetNumberOfDigits (unsigned i)
{
return i > 0 ? (int) log10 ((double) i) + 1 : 1;
}
log10 определяется в <cmath> или <math.h>. Вам нужно будет профилировать это, чтобы увидеть, быстрее ли это, чем кто-либо из других, размещенных здесь. Я не уверен, насколько это важно в отношении точности точки плавания. Кроме того, аргумент не обозначен как отрицательные значения, а журнал не смешивается.
Ответ 3
Возможно, я неправильно понял вопрос, но разве это не так?
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)))))))));
}
Ответ 4
int digits = 0; while (number != 0) { number /= 10; digits++; }
Примечание: "0" будет содержать 0 цифр! Если вам нужно 0, чтобы иметь 1 цифру, используйте:
int digits = 0; do { number /= 10; digits++; } while (number != 0);
(Спасибо, Кевин Феган)
В конце концов, используйте профилировщик, чтобы узнать, какой из ответов здесь будет быстрее на вашем компьютере...
Ответ 5
Практическая шутка: Это самый эффективный способ (количество цифр вычисляется во время компиляции):
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 };
};
Может быть полезно определить ширину, необходимую для поля чисел в форматировании, элементах ввода и т.д.
Ответ 6
Смотрите Bit Twiddling Hacks для более короткой версии ответа, который вы приняли. Он также имеет преимущество поиска ответа раньше, если ваш вход обычно распределяется, сначала проверяя большие константы. (v >= 1000000000) улавливает 76% значений, поэтому проверка этого будет в среднем быстрее.
Ответ 7
конвертировать в строку, а затем использовать встроенные функции
unsigned int i;
cout<< to_string(i).length()<<endl;
Ответ 8
Предыдущий плакат предложил цикл, который делит на 10. Поскольку множители на современных машинах намного быстрее, я бы рекомендовал вместо этого следующий код:
int digits = 1, pten=10; while ( pten <= number ) { digits++; pten*=10; }
Ответ 9
В архитектуре 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, но другие архитектуры должны иметь схожие инструкции.
Ответ 10
int x = 1000;
int numberOfDigits = x ? static_cast<int>(log10(abs(x))) + 1 : 1;
Ответ 11
#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 равно 1 цифре.
Ответ 12
#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 [email protected]
/// - \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
)
)
);
}
Ответ 13
Мне нравится Ирак Бакстер. Вот шаблонный вариант, который обрабатывает различные размеры и имеет дело с максимальными целыми значениями (обновляется, чтобы поднять верхнюю границу проверки цикла):
#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 стоит больше, чем тесты, удаленные из цикла.
Я оставлю все это как упражнение для читателя.
Ответ 14
/// Determine the number of digits for a 64 bit integer.
/// - Uses at most 5 comparisons.
/// - (cX) 2014 [email protected]
/// - \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
)
)
)
);
}
Ответ 15
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, и если бы существовало знание о том, что будет кластеризация, но не знание того, где кластер может быть, возможно, саморегулирующейся деревом, может быть лучше
Ответ 16
эффективный способ
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;
}
Ответ 17
Еще один фрагмент кода, делающий в основном то же самое, что и Vitali, но использует двоичный поиск. Массив Powers lazy инициализируется один раз на экземпляр без знака. Перегрузка подписи вызывает знак "минус".
#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 раза.
Ответ 18
в случае, если количество цифр AND необходимо для каждого значения цифр использовать следующее:
int64_t = number, digitValue, digits = 0; // or "int" for 32bit
while (number != 0) {
digitValue = number % 10;
digits ++;
number /= 10;
}
digit дает вам значение в постулировании числа, которое в настоящее время обрабатывается в цикле. например, для номера 1776 значение цифры:
6 в 1-м цикле
7 во втором цикле
7 в третьем цикле
1 в 4-м цикле
Ответ 19
С++ 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, et. и др.
Ответ 20
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;
}
Ответ 21
// 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) );
Ответ 22
int numberOfDigits(int n){
if(n<=9){
return 1;
}
return 1 + numberOfDigits(n/10);
}
Это то, что я бы сделал, если вы хотите это для базы 10. Это довольно быстро, и вы, скорее всего, не получите оверлок стека, подсчитывающий целые числа
Ответ 23
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";
Ответ 24
Если быстрее, тем эффективнее, это улучшение по Андрею Александру. Его версия была уже быстрее, чем наивный способ (деление на 10 на каждую цифру). Приведенная ниже версия имеет постоянное время и быстрее, по крайней мере, для x86-64 и ARM для всех размеров, но занимает в два раза больше двоичного кода, поэтому она не так удобна для кэша.
Тесты для этой версии против alexandrescu версии на моем PR на фоллике в facebook.
Работает на 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);
}
Ответ 25
Используя журнал:
floor( log10(n) ) + 1
Ответ 26
для целого числа "X" вы хотите знать количество цифр, если не использовать какой-либо цикл, это решение действует в одной формуле только в одной строке, так что это наиболее оптимальное решение, которое я когда-либо видел в этой проблеме.
int x = 1000 ;
cout<<numberOfDigits = 1+floor(log10(x))<<endl ;
Ответ 27
Это мой способ сделать это:
int digitcount(int n)
{
int count = 1;
int temp = n;
while (true)
{
temp /= 10;
if (temp != 0) ++count;
if (temp == 0) break;
}
return count;
}
Ответ 28
Здесь другой подход:
digits = sprintf(numArr, "%d", num); // where numArr is a char array
if (num < 0)
digits--;
Это может быть неэффективно, просто что-то отличное от того, что предложили другие.