Проверка того, является ли число мощностью 10

Есть ли лучший способ проверить, является ли число мощностью 10? Это то, что я реализовал:

    public class PowersOfTen {

    public static boolean isPowerOfTen(long input) {

        if (input % 10 != 0 || input == 0) {
            return false;
        }

        if (input == 10) {
            return true;
        }

        return isPowerOfTen(input/10);
    }

    public static void main(String[] args) {

        System.out.println("1000: " + isPowerOfTen(1000));
        System.out.println("4: " + isPowerOfTen(4));
        System.out.println("0: " + isPowerOfTen(0));
        System.out.println("10: " + isPowerOfTen(10));
        System.out.println("100: " + isPowerOfTen(100));
    }
}
34 голоса | спросил jcm 19 Jam1000000amTue, 19 Jan 2016 03:38:20 +030016 2016, 03:38:20

12 ответов


39

Рекурсия кажется довольно тяжелой для этого. Вы можете использовать ту же логику, но с помощью простого цикла:

while (input > 9 && input % 10 == 0) 
  input /= 10;
return input == 1;

Это проверяет, что вход положительный (поскольку отрицательные числа и ноль не могут быть степенями 10) и кратным 10 (поскольку все степени 10 больше 1, очевидно, есть). Сначала он позитивно оценивается как небольшая микро-оптимизация; оценка короткого замыкания позволит избежать ненужного деления для вычисления ненужного модуля.

Если оба условия выполнены, он выполняет целочисленное деление на 10 и повторяет этот процесс. При любой мощности 10 это будет заканчиваться значением 1; если 1 сам передан, он сделает это, не выполняя тело цикла while.

ответил Mark Reed 19 Jam1000000amTue, 19 Jan 2016 04:00:46 +030016 2016, 04:00:46
36

Вы также можете просто перечислить их, так как в длинном типе данных не так много.

Преимущества над кодом в OP - это просто, понятно и правильно.

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

public static boolean isPowerOfTen(long input) {
  return 
    input == 1L
  || input == 10L
  || input == 100L
  || input == 1000L
  || input == 10000L
  || input == 100000L
  || input == 1000000L
  || input == 10000000L
  || input == 100000000L
  || input == 1000000000L
  || input == 10000000000L
  || input == 100000000000L
  || input == 1000000000000L
  || input == 10000000000000L
  || input == 100000000000000L
  || input == 1000000000000000L
  || input == 10000000000000000L
  || input == 100000000000000000L
  || input == 1000000000000000000L;
}   
ответил Martin Smith 19 Jpm1000000pmTue, 19 Jan 2016 22:23:38 +030016 2016, 22:23:38
30

Я считаю ваш код неправильным, потому что я ожидаю, что isPowerOfTen(1) будет true.

ответил 200_success 19 Jam1000000amTue, 19 Jan 2016 04:01:26 +030016 2016, 04:01:26
13

Математическая альтернатива

Math.log10() :

public static boolean isPowerOfTen(long value) {
    // updated answer - check for precision in if statement
    if (value >= 1e14) {
        try {
            return isPowerOfTen(BigDecimal.valueOf(value)
                                    .divide(BigDecimal.valueOf(1e14)).longValueExact());
        } catch (ArithmeticException e) {
            return false;
        }
    }
    double power = Math.log10(value);
    return Double.isFinite(power) && Math.round(power) == power;
}

Соблюдайте точность , как указано в @ комментарий ErickWong . Я обновил свой ответ выше, чтобы обрабатывать значения выше 1e14, который, кажется, является точкой, где точность теряется.

Тестирование модулей

Ваши простые тесты в main() должны быть преобразованы в форму единичный тест . Например, используя TestNG :

public void testPowerOfTen() {
    assertTrue(isPowerOfTen(1)); // 10^0, as mentioned by @200_success
    assertTrue(isPowerOfTen(1000));
    assertFalse(isPowerOfTen(4));
    assertFalse(isPowerOfTen(0));
    assertTrue(isPowerOfTen(10));
    assertTrue(isPowerOfTen(100));
}
ответил h.j.k. 19 Jam1000000amTue, 19 Jan 2016 06:08:40 +030016 2016, 06:08:40
8

В том же духе, что и ответ Мартина Смита, вы можете хранить все мощности 10 по порядку в массиве и затем выполнять двоичный поиск:

private static final long[] powersOf10 = new long[] {
    1L, 10L, 100L, 1000L, 10000L, 100000L, 1000000L, 10000000L,
    100000000L, 1000000000L, 10000000000L, 100000000000L,
    1000000000000L, 10000000000000L, 100000000000000L, 1000000000000000L,
    10000000000000000L, 100000000000000000L, 1000000000000000000L
};

static boolean isPowerOfTen(long input) {
    return Arrays.binarySearch(powersOf10, input) >= 0;
}

Примечание: этот метод far менее эффективен, чем у Мартина (примерно на 2.5x как на моем компьютере) для этого небольшого набора данных, но он намного лучше масштабируется для больших наборов данных.

С другой стороны, если вам нужна экстремальная скорость, то этот алгоритм, основанный на комментарии 5gon12eder, может стоить того. Он включает младшие бит ввода (вы не можете включить длинный), и если он получает удар, он выполняет линейный поиск.

static boolean isPowerOfTen(long input) {
    switch ((int)input) {
        case (int)1L:
        case (int)10L:
        case (int)100L:
        case (int)1000L:
        case (int)10000L:
        case (int)100000L:
        case (int)1000000L:
        case (int)10000000L:
        case (int)100000000L:
        case (int)1000000000L:
        case (int)10000000000L:
        case (int)100000000000L:
        case (int)1000000000000L:
        case (int)10000000000000L:
        case (int)100000000000000L:
        case (int)1000000000000000L:
        case (int)10000000000000000L:
        case (int)100000000000000000L:
        case (int)1000000000000000000L:
            return linearSearch(input);
        default:
            return false;
    }
}

// from Martin Smith's answer:
private static boolean linearSearch(long input) {
    return
        input == 1L
            || input == 10L
            || input == 100L
            || input == 1000L
            || input == 10000L
            || input == 100000L
            || input == 1000000L
            || input == 10000000L
            || input == 100000000L
            || input == 1000000000L
            || input == 10000000000L
            || input == 100000000000L
            || input == 1000000000000L
            || input == 10000000000000L
            || input == 100000000000000L
            || input == 1000000000000000L
            || input == 10000000000000000L
            || input == 100000000000000000L
            || input == 1000000000000000000L;
}

Сравнительные вычисления на первые миллиарды положительных цепей:

  • линейный поиск (Martin Smith): 2970 мс
  • двоичный поиск: 6908 мс
  • включить хэш, а затем линейный поиск: 1519 мс
ответил Solomonoff's Secret 20 Jpm1000000pmWed, 20 Jan 2016 21:14:11 +030016 2016, 21:14:11
3

Итеративная версия

Это предложение похоже на ответ @ 200_success. Это может быть заключено в цикл for-loop, если вы занимаетесь этим делом :). Достопримечательности:

  • Нет рекурсии. Рекурсия делает для элегантного кода, но эти дополнительные вызовы функций по сравнению с итеративной функцией иногда вызывают значительное снижение производительности.
  • Использование умножения вместо деления (которое должно быть быстрее, но я не авторитет в этом)
  • Нет специальной обработки 0, 1 или отрицательных input номеров. База нуждается в проверке.
  • Можно использовать другие базы, чем 10.

Java:

public static boolean isPowerOf(long input, long base) {
    if (base < 2) throw new IllegalArgumentException("base must be 2 or larger");
    //find the biggest number that is safe to multiply base with without getting integer oveflow
    long safeMultiplier = Long.MAX_VALUE / base;
    long x = 1;
    while (x < input && x <= safeMultiplier) {
        x *= base;
    }
    return x == input;
}

Версия BigInteger

Потому что иногда Long достаточно недолго:)

public static boolean isPowerOf(BigInteger input, BigInteger base) {
    if (base.compareTo(BigInteger.ONE) != 1) {
        throw new IllegalArgumentException("base must be 2 or larger");
    }
    BigInteger x = BigInteger.ONE;
    int comparison;
    while ((comparison = x.compareTo(input)) == -1) {
        x = x.multiply(base);
    }
    return comparison == 0;
}

Рекурсивная версия

Рекурсивная версия все еще использует умножение вместо деления. Включение рекурсивного вызова в функцию (например, вы также сделали) - это кивок в отношении языков, которые могут выполнять оптимизацию хвостовых вызовов ( http://c2.com/cgi/wiki?TailCallOptimization & https: //ru .wikipedia.org /вики /Tail_call ). Я не думаю, что Java это делает.

public static boolean recursiveIsPowerOf(long input, long base) {
    if (base < 2) throw new IllegalArgumentException("base must be 2 or larger");
    //find the biggest number that is safe to multiply base with without getting integer oveflow
    long safeMultiplier = Long.MAX_VALUE / base;
    if (safeMultiplier < base)
        return input == base;

    return recursiveIsPowerOf(input, base, 1);
}

private static boolean recursiveIsPowerOf(long input, long base, long x) {
    return (x >= input || x < 0) ? x == input : recursiveIsPowerOf(input, base, x * base);
}

Edit (s):

  • Добавлена ​​проверка переполнения целых чисел в соответствии с предложением ErickWong
  • Добавлена ​​проверка действительной базы (> 1)
  • Добавлена ​​версия BigInteger
  • Исправлены ошибки проверки переполнения.
ответил Max 19 Jpm1000000pmTue, 19 Jan 2016 19:47:38 +030016 2016, 19:47:38
2

Нет делений, нет модулей, нет рекурсии? Здесь мы идем:

public static boolean power10(int n) {
    int max_power10 = 100000; //whatever you can accept given your type
    int i = 1;
    while ( i != n && i != max_power10) i *= 10;   
    return i == n;
}

Улучшение:

public static boolean power10(int n) {
    int max_power10 = 100000; //whatever you can accept given your type
    if (n > max_power10 ) return false;
    int i = 1;
    while (i < n) i *= 10;   
    return i == n;
}
ответил DarioP 20 Jpm1000000pmWed, 20 Jan 2016 14:43:53 +030016 2016, 14:43:53
1

ИМО это было бы чище, как:

public static boolean isPowerOfTen(long input) {
    if (input <= 0 ) {
        // powers of 10 can't be 0 or negative
        return false;
    }

    // don't have to worry about negative powers since long input
    // doesn't hold fractions
    for (int pow = 0; pow <= Math.log10(Long.MAX_VALUE); ++pow) {
        if (input == (long)Math.pow(10, pow)) {
            return true;
        }
    }
    return false;
}

Math.log10 (Long.MAX_VALUE) даст максимальную мощность 10, которая будет вписываться в длину, пол которой (усечен неявным преобразованием) 18.

Отсюда также можно легко сделать общий метод, заменив ссылки на 10 и Math.log10. Java не имеет метода Math.logb, но напомните: logb (x) = logc (x) /logc (b). Итак, logb (Long.MAX_VALUE) = Math.log (Long. MAX_VALUE) /Math.log (b):

public static boolean isPowerOf(long input, int base) {
    if (input <= 0 ) {
        return false;
    }

    for (int pow = 0; pow <= Math.log(Long.MAX_VALUE) / Math.log(base); ++pow) {
        if (input == Math.floor(Math.pow(base, pow))) {
            return true;
        }
    }
    return false;
}

Но мы также можем исключить цикл с небольшой математикой, чтобы найти мощность напрямую и проверить, является ли она целым числом:

public static boolean isPowerOf(long input, int base) {
    if (input == 0) {
        return false;
    }

    // use Math.abs since if the argument is NaN or less than zero to Math.log, 
    // then the result is NaN. This makes it work for negative inputs and bases
    Double power = Math.log(Math.abs(input)) / Math.log(Math.abs(base));

    // power might have lost precision, so I'm trying floor and ceiling. These are integers so if either yields the input, return true
    return (input == (long)Math.pow(base, Math.floor(power)) ||
            input == (long)Math.pow(base,  Math.ceil(power)));
}
ответил Brad E 19 Jpm1000000pmTue, 19 Jan 2016 13:15:34 +030016 2016, 13:15:34
1

Это для удовольствия, но как насчет этого самого основного решения?:

String.valueOf(x).matches("^10*$")

Он также должен работать для long и BigDecimal с помощью toPlainString().

Кстати, я знаю, что это не высокая производительность: P.

Также как любопытство любая сила 10 в двоичном представлении заканчивается сама собой:

1 -> b'1'
10 -> b'x10'
100 -> b'x100'
1000 -> b'x1000'
...

(где x - последовательность «1» и «0»)

ответил FranMowinckel 25 Jpm1000000pmMon, 25 Jan 2016 20:28:09 +030016 2016, 20:28:09
1

Итерация будет более эффективной, чем рекурсия.

Также input == 1 должен считаться мощностью 10.

public static boolean isPowerOfTen(long input) {
    while (input > 1) {
        if (input % 10 != 0)
            return false;
        input = input / 10;
    }

    if (input == 1) {
        return true;
    }

    return false;
}

Даже более короткая версия (предложенная Landei - спасибо!):

public static boolean isPowerOfTen(long input) {
    while (input > 1) {
        if (input % 10 != 0)
            return false;
        input /= 10;
    }

    return input == 1;
}
ответил CiaPan 19 Jpm1000000pmTue, 19 Jan 2016 14:01:06 +030016 2016, 14:01:06
0

Вот один из них, если мы хотим избежать разветвления CPU, что было бы неплохо в компилируемых языках, таких как C или C ++, для процессоров, имеющих широкие конвейеры. Он подсчитывает все не-нули и единицы в базе 10.

Идея такова: тогда и только тогда, когда не существует более крупных и ровно один, тогда мы имеем степень 10.

int ispow10(int aInput){
  int lCntO = 0, lCnt1 = 0, lTmp = 0, i = 0;
  for( i=0 ;i < 10; i++, aInput /= 10 ){
    lTmp = aInput % 10;
    lCntO += (lTmp > 1);
    lCnt1 += (lTmp == 1);
  }
return (lCntO == 0)&(lCnt1==1);
}
ответил mathreadler 21 Jam1000000amThu, 21 Jan 2016 08:24:53 +030016 2016, 08:24:53
-1

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

boolean isPowerOfTen(int n) {
    char[] digits = (n+"").toCharArray();
    if (digits[0] != '1') return false;
    for (int i = 1; i<digits.length; i++) {
      if (digits[i] != '0') return false;
    }
    return true;
}

Вы можете легко расширить его для отрицательных мощностей (0.000001), и его, возможно, намного легче читать и сокращать, чем другие методы, хотя он имеет худшую производительность.

ответил Diego Martinoia 19 Jpm1000000pmTue, 19 Jan 2016 17:06:55 +030016 2016, 17:06:55

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132