Используйте неподписанный, когда столбец будет только предназначен для содержания положительных чисел.
Это не будет влиять ни на какую производительность ввода-вывода на столбце, поскольку это все еще поднимет точно ту же сумму пространства.
Что ж, наиболее эффективным способом, предполагающим, что вы знаете размер целого числа, будет поиск. Должен быть быстрее, чем подход, основанный на гораздо более коротком логарифме. Если вас не интересует подсчет «-», удалите + 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];
}
Предыдущий плакат предлагал цикл, который делится на 10. Поскольку умножение на современных машинах происходит намного быстрее, я бы порекомендовал вместо этого следующий код:
int digits = 1, pten=10; while ( pten <= number ) { digits++; pten*=10; }
Practical joke: Это наиболее эффективный способ (количество цифр вычисляется во время компиляции):
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 };
};
Может быть полезно для определения ширины, необходимой для числового поля при форматировании, элементах ввода и т. Д.
int digits = 0; while (number != 0) { number /= 10; digits++; }
Примечание: «0» будет содержать 0 цифр! Если вам нужно, чтобы 0 выглядело как 1 цифра, используйте:
int digits = 0; do { number /= 10; digits++; } while (number != 0);
(Спасибо, Кевин Феган)
В конце концов, используйте профилировщик, чтобы узнать, какой из всех ответов здесь будет быстрее на вашем компьютере ...
Самый простой способ - это сделать:
unsigned GetNumberOfDigits (unsigned i)
{
return i > 0 ? (int) log10 ((double) i) + 1 : 1;
}
log10 определен в
или
. Вам нужно будет профилировать это, чтобы увидеть, быстрее ли он, чем любой из других размещенных здесь. Я не уверен, насколько это надежно в отношении точности с плавающей запятой. Кроме того, аргумент беззнаковый, поскольку отрицательные значения и журнал действительно не смешиваются.
Here's a different approach:
digits = sprintf(numArr, "%d", num); // where numArr is a char array
if (num < 0)
digits--;
This may not be efficient, just something different than what others suggested.
эффективный способ
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;
}
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);
}
};
where in powers_and_max
we have (10^n)-1
for all n
such that
(10^n) <
std::numeric_limits
and std::numeric_limits
in an 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());
}
};
here's a simple 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);
Of course any other implementation of an ordered set might be used for powers_and_max
and if there was knowledge that there would be clustering but no knowledge of where the cluster might be perhaps a self adjusting tree implementation might be best
The ppc architecture has a bit counting instruction. With that, you can determine the log base 2 of a positive integer in a single instruction. For example, 32 bit would be:
#define log_2_32_ppc(x) (31-__cntlzw(x))
If you can handle a small margin of error on large values you can convert that to log base 10 with another few instructions:
#define log_10_estimate_32_ppc(x) (9-(((__cntlzw(x)*1233)+1545)>>12))
This is platform specific and slightly inaccurate, but also involves no branches, division or conversion to floating point. All depends on what you need.
I only know the ppc instructions off hand, but other architectures should have similar instructions.
Perhaps I misunderstood the question but doesn't this do it?
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)))))))));
}
Мне нравится ответ Иры Бакстера. Вот вариант шаблона, который обрабатывает различные размеры и имеет дело с максимальными целочисленными значениями (обновлено, чтобы поднять верхнюю границу проверки вне цикла):
#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 стоит больше, чем тесты, удаленные из цикла.
Я оставлю все это в качестве упражнения для читателя.
См. Bit Twiddling Hacks для более короткой версии принятого вами ответа. Кроме того, он позволяет быстрее находить ответ, если ваш ввод обычно распределяется, путем проверки сначала больших констант. (v> = 1000000000)
захватывает 76% значений, поэтому проверка первого будет в среднем быстрее.