Перейти к основному содержимому

Количество цифр в целом числе в Java

· 5 мин. чтения

Упражнение: Сложение двух чисел

Даны два неотрицательный целых числа в виде непустых связных списков. Их цифры хранятся в обратном порядке. И каждый елемент списка содержить ровно одну цифру. Сложите эти два числа и верните сумму в виде связного списка ...

ANDROMEDA

1. Введение

В этом кратком руководстве мы рассмотрим различные способы получения количества цифр в Integer в Java.

Мы также проанализируем различные методы, чтобы выяснить, какой алгоритм лучше всего подходит для каждой ситуации.

2. Количество цифр в целом числе

Для обсуждаемых здесь методов мы рассматриваем только положительные целые числа. Если мы ожидаем какой-либо отрицательный ввод, то мы можем сначала использовать Math.abs(number) перед использованием любого из этих методов.

2.1. Строковое решение

Возможно, самый простой способ получить количество цифр в Integer — преобразовать его в String и вызвать метод length() . Это вернет длину строкового представления нашего числа:

int length = String.valueOf(number).length();

Однако это может быть неоптимальным подходом, поскольку этот оператор включает выделение памяти для строки для каждой оценки. JVM должна разобрать наш номер и скопировать его цифры в отдельную строку, а также выполнить ряд других различных операций (например, сохранить временные копии, обработать преобразования Unicode и т. д.).

Если у нас есть только несколько чисел для оценки, мы можем использовать это решение, потому что разница между этим и любым другим подходом будет незначительной даже для больших чисел.

2.2. Логарифмический подход

Для чисел, представленных в десятичной форме, если мы возьмем их логарифм по основанию 10 и округлим его в большую сторону, мы получим количество цифр в этом числе:

int length = (int) (Math.log10(number) + 1);

Обратите внимание, что log 10 0 любого числа не определен, поэтому, если мы ожидаем каких-либо входных данных со значением 0 , мы также можем поставить проверку для этого.

Логарифмический подход значительно быстрее, чем подход, основанный на String , поскольку ему не нужно проходить процесс преобразования данных. Это просто включает в себя простой, прямой расчет без какой-либо дополнительной инициализации объекта или циклов.

2.3. Повторное умножение

В этом методе мы возьмем временную переменную (с инициализацией 1) и непрерывно умножим ее на 10, пока она не станет больше нашего числа. Во время этого процесса мы также будем использовать переменную длины , которая будет отслеживать длину числа:

int length = 0;
long temp = 1;
while (temp <= number) {
length++;
temp *= 10;
}
return length;

В этом коде temp *= 10 равносильно написанию temp = (temp << 3) + (temp << 1) . Поскольку умножение обычно является более затратной операцией на некоторых процессорах по сравнению с операторами сдвига, последние могут быть немного более эффективными.

2.4. Деление со степенью двойки

Если мы знаем диапазон нашего числа, то мы можем использовать вариант, который еще больше уменьшит наши сравнения. Этот метод делит число на степени двойки (например, 1, 2, 4, 8 и т. д.):

int length = 1;
if (number >= 100000000) {
length += 8;
number /= 100000000;
}
if (number >= 10000) {
length += 4;
number /= 10000;
}
if (number >= 100) {
length += 2;
number /= 100;
}
if (number >= 10) {
length += 1;
}
return length;

Он использует тот факт, что любое число может быть представлено сложением степеней двойки. Например, 15 можно представить как 8+4+2+1, которые являются степенями двойки.

Для 15-значного числа мы бы сделали 15 сравнений в нашем предыдущем подходе, по сравнению с четырьмя в этом методе.

2.5. Разделяй и властвуй

Это, пожалуй, самый громоздкий подход по сравнению со всеми другими, описанными здесь; однако это также и самое быстрое , потому что мы не выполняем никакого преобразования, умножения, сложения или инициализации объекта.

Мы можем получить ответ всего за три-четыре простых оператора if :

if (number < 100000) {
if (number < 100) {
if (number < 10) {
return 1;
} else {
return 2;
}
} else {
if (number < 1000) {
return 3;
} else {
if (number < 10000) {
return 4;
} else {
return 5;
}
}
}
} else {
if (number < 10000000) {
if (number < 1000000) {
return 6;
} else {
return 7;
}
} else {
if (number < 100000000) {
return 8;
} else {
if (number < 1000000000) {
return 9;
} else {
return 10;
}
}
}
}

Как и в предыдущем подходе, мы можем использовать этот метод, только если знаем диапазон нашего числа.

3. Сравнительный анализ

Теперь, когда у нас есть хорошее представление о возможных решениях, давайте проведем простой бенчмаркинг наших методов с помощью Java Microbenchmark Harness (JMH) .

В следующей таблице показано среднее время обработки каждой операции (в наносекундах):

Benchmark                            Mode  Cnt   Score   Error  Units
Benchmarking.stringBasedSolution avgt 200 32.736 ± 0.589 ns/op
Benchmarking.logarithmicApproach avgt 200 26.123 ± 0.064 ns/op
Benchmarking.repeatedMultiplication avgt 200 7.494 ± 0.207 ns/op
Benchmarking.dividingWithPowersOf2 avgt 200 1.264 ± 0.030 ns/op
Benchmarking.divideAndConquer avgt 200 0.956 ± 0.011 ns/op

Решение на основе String , которое является самым простым, также является наиболее дорогостоящей операцией, поскольку только оно требует преобразования данных и инициализации новых объектов.

Логарифмический подход значительно эффективнее предыдущего решения, поскольку не требует преобразования данных. Кроме того, будучи однострочным решением, он может быть хорошей альтернативой подходу на основе строк.

Повторное умножение включает простое умножение пропорционально длине числа; например, если число состоит из 15 цифр, то этот метод будет включать 15 умножений.

Однако уже следующий метод использует тот факт, что каждое число может быть представлено степенью двойки (подход, аналогичный BCD). Он сводит то же уравнение к четырем операциям деления, поэтому он даже более эффективен, чем первый.

Наконец, как мы можем сделать вывод, наиболее эффективным алгоритмом является многословная реализация «Разделяй и властвуй», которая выдает ответ всего за три-четыре простых оператора if . Мы можем использовать его, если у нас есть большой набор данных, который нам нужно проанализировать.

4. Вывод

В этой краткой статье мы описали некоторые способы определения количества цифр в целом числе и сравнили эффективность каждого подхода.

Как всегда, полный код доступен на GitHub .