Как проверить, является ли целое число степенью 3?

Question

Я видел этот вопрос , и всплыла эта идея.

Answer 1

while (n % 3 == 0) {
    n /= 3;
}
return n == 1;

Обратите внимание, что 1 - нулевая степень трех.

Редактировать: Вам также нужно проверить на ноль перед циклом, так как цикл не завершится при n = 0 (спасибо Бруно Ротгиссеру).

Answer 2

Существует метод с постоянным временем (довольно быстрый) для целых чисел ограниченного размера (например, 32-разрядных целых).

Обратите внимание, что для целого числа N, равного 3, верно следующее:

1. Для любого M <= N, который является степенью 3, M делит N.
2. Для любого M <= N, не являющегося степенью 3, M не делит N.

Наибольшая степень 3, которая умещается в 32 бита, равна 3486784401 (3^20). Это дает следующий код:

bool isPower3(std::uint32_t value) {
    return value != 0 && 3486784401u % value == 0;
}

Аналогично для 32 бит со знаком это 1162261467 (3^19):

bool isPower3(std::int32_t value) {
    return value > 0 && 1162261467 % value == 0;
}

В общем, магическое число:

== pow(3, floor(log(MAX) / log(3)))

Осторожнее с ошибками округления с плавающей запятой, используйте математический калькулятор, например Wolfram Alpha , чтобы вычислить константу. Например, для 2^63-1 (со знаком int64) и C ++, и Java дают 4052555153018976256, но правильное значение равно 4052555153018976267.

Answer 3

Я чувствую себя слегка , думая, что если под "целым числом" вы подразумеваете "32-разрядное целое число со знаком", то (псевдокод)

return (n == 1) 
    or (n == 3)
    or (n == 9)
    ... 
    or (n == 1162261467) 

имеет определенную красивую простоту (последнее число 3 ^ 19, поэтому не бывает абсурдного числа случаев). Даже для 64-разрядного целого числа без знака все еще будет только 41 случай (спасибо @Alexandru за то, что указал мне на промах в мозгу). И, конечно, было бы невозможно для арифметики произвольной точности ...

Answer 4

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

Следующий алгоритм в среднем быстрее, а в некоторых случаях значительно быстрее, чем простой цикл while(n%3==0) n/=3;:

bool IsPowerOfThree(uint n)
{
  // Optimizing lines to handle the most common cases extremely quickly
  if(n%3 != 0) return n==1;
  if(n%9 != 0) return n==3;

  // General algorithm - works for any uint
  uint r;
  n = Math.DivRem(n, 59049, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r, 243, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r,  27, out r); if(n!=0 && r!=0) return false;
  n += r;
  return n==1 || n==3 || n==9;
}

Числовые константы в коде: 3 ^ 10, 3 ^ 5 и 3 ^ 3.

Расчет производительности

В современных процессорах DivRem часто представляет собой одну инструкцию, которая занимает один цикл. В других случаях он расширяется до div, за которым следует mul и add, что в целом занимает больше трех циклов. Каждый шаг общего алгоритма выглядит длинным, но на самом деле он состоит только из: DivRem, cmp, cmove, cmp, cand, cjmp, add. Доступно много параллелизма, поэтому на типичном двухстороннем суперскалярном процессоре каждый шаг, вероятно, будет выполняться примерно за 4 такта, обеспечивая гарантированное время выполнения в худшем случае около 25 тактов.

Если входные значения равномерно распределены по диапазону UInt32, вот вероятности, связанные с этим алгоритмом:

• Возврат в или до первой строки оптимизации: 66% времени
• Возврат во или до второй строки оптимизации: 89% времени
• Возврат в или до первого общего шага алгоритма: 99,998% времени
• Возврат во второй шаг общего алгоритма или до него: 99,99999% времени
• Возврат в или до третьего общего шага алгоритма: 99,999997% времени

Этот алгоритм превосходит простой цикл while(n%3==0) n/=3, который имеет следующие вероятности:

• Возврат в первой итерации: 66% времени
• Возврат в первые две итерации: 89% времени
• Возврат в первые три итерации: 97% времени
• Возврат в первые четыре итерации: 98,8% времени
• Возврат в первые пять итераций: 99,6% времени ... и так далее ...
• Возврат в первые двенадцать итераций: 99,9998% времени ... и далее ...

Что, возможно, еще важнее, этот алгоритм обрабатывает средние и большие степени трех (и их кратные) намного более эффективно: в худшем случае простой алгоритм потребляет более 100 циклов ЦП, поскольку цикл 20 раз (41 раз для 64 бит). Алгоритм, который я здесь представляю, никогда не займет больше 25 циклов.

Расширение до 64 бит

Расширение вышеупомянутого алгоритма до 64 битов тривиально - просто добавьте еще один шаг. Вот 64-битная версия вышеупомянутого алгоритма, оптимизированная для процессоров без эффективного 64-битного разделения:

bool IsPowerOfThree(ulong nL)
{
  // General algorithm only
  ulong rL;
  nL = Math.DivRem(nL, 3486784401, out rL); if(nL!=0 && rL!=0) return false;
  nL = Math.DivRem(nL+rL,   59049, out rL); if(nL!=0 && rL!=0) return false;
  uint n = (uint)nL + (uint)rL;
  n = Math.DivRem(n,   243, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r,  27, out r); if(n!=0 && r!=0) return false;
  n += r;
  return n==1 || n==3 || n==9;

}

Новая константа 3 ^ 20. Строки оптимизации опущены в верхней части метода, потому что при нашем предположении, что 64-битное деление медленное, они на самом деле замедляют процесс.

Почему эта техника работает

Скажем, я хочу знать, является ли "100000000000000000" степенью 10. Я мог бы выполнить следующие шаги:

1. Я делю на 10 ^ 10 и получаю частное 10000000 и остаток 0. Это добавляет к 10000000.
2. Я делю на 10 ^ 5 и получаю частное 100 и остаток 0. Они добавляют к 100.
3. Я делю на 10 ^ 3 и получаю частное 0 и остаток 100. Они добавляют к 100.
4. Я делю на 10 ^ 2 и получаю частное 1 и остаток 0. Они добавляют к 1.

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

В этом примере я выбрал показатели 10, 5 и 3, чтобы соответствовать коду, предоставленному ранее, и добавил 2 только для этого. Другие показатели также будут работать: существует простой алгоритм выбора идеальных показателей, учитывая ваше максимальное входное значение и максимальную мощность 10, допустимую в выходных данных, но у этого поля недостаточно места для его хранения.

ПРИМЕЧАНИЕ: Вы, возможно, думали на десятой базе в течение всего этого объяснения, но все объяснение выше можно прочитать и понять одинаково, если вы думаете на третьей базе , за исключением показателей выраженные по-разному (вместо «10», «5», «3» и «2» я бы сказал «101», «12», «10» и «2»).

Answer 5

если (log n) / (log 3) является целым числом, тогда n является степенью 3.

Answer 6

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

private bool IsPow3(int n)
{
    if (n == 0) return false;
    while (n % 9 == 0)
    {
        n /= 9;
    }
    return (n == 1 || n == 3);
}

Answer 7

Рекурсивно разделить на 3, проверить, что остаток равен нулю, и повторно применить к частному.

Обратите внимание, что 1 является верным ответом, а 3 для нулевой степени - 1, это крайний случай, о котором следует помнить.

Answer 8

Это сводка всех хороших ответов ниже этих вопросов, а показатели производительности можно найти в статье LeetCode .

1. Итерация цикла

Сложность времени O (log (n)), сложность пространства O (1)

public boolean isPowerOfThree(int n) {
    if (n < 1) {
        return false;
    }

    while (n % 3 == 0) {
        n /= 3;
    }

    return n == 1;
}

2. Базовая конверсия

Преобразуйте целое число в число 3 основания и проверьте, записано ли оно как начальная 1, за которой следуют все 0. Это решение вдохновляет решение проверить, является ли число степенью 2, выполнив n & (n - 1) == 0

Сложность времени: O (log (n)) в зависимости от языка и компилятора, сложность пространства: O (log (n))

public boolean isPowerOfThree(int n) {
    return Integer.toString(n, 3).matches("^10*$");
}

3 Математика

Если n = 3^i, то i = log(n) / log(3), и, таким образом, приходит к решению

Сложность времени: в зависимости от языка и компилятора, сложность пространства: O (1)

public boolean isPowerOfThree(int n) {
    return (Math.log(n) / Math.log(3) + epsilon) % 1 <= 2 * epsilon;
}

4 Целочисленные ограничения

Поскольку 3^19 = 1162261467 является наибольшей степенью 3-х чисел в 32-битном целом, мы можем сделать

Сложность времени: O (1), сложность пространства: O (1)

public boolean isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}

5 Целочисленные ограничения с Set

Идея похожа на # 4, но использует набор для хранения всех возможных степеней 3 чисел (от 3 ^ 0 до 3 ^ 19). Это делает код более читабельным.

6 Рекурсивно (C ++ 11)

Это решение относится только к C ++ 11 и использует шаблонное метапрограммирование, так что complier заменяет вызов isPowerOf3<Your Input>::cValue на вычисленный результат.

Сложность времени: O (1), сложность пространства: O (1)

template<int N>
struct isPowerOf3 {
    static const bool cValue = (N % 3 == 0) && isPowerOf3<N / 3>::cValue;
};

template<>
struct isPowerOf3<0> {
    static const bool cValue = false;
};

template<>
struct isPowerOf3<1> {
    static const bool cValue = true;
};

int main() {
    cout<<isPowerOf3<1162261467>::cValue;
    return 0;
}

Answer 9

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

1. Найдите двоичный логарифм n, найдя позицию старшего бита 1 в числе. Это очень быстро, так как современные процессоры имеют специальную инструкцию для этого. (В противном случае вы можете сделать это с помощью битовых твидлингов, см. Битовые тэдлинг хаки ).

2. Найдите потенциальную степень три в таблице, индексированной по этой позиции, и сравните с n (если нет степени три, вы можете сохранить любое число с другим двоичным логарифмом). 1015 *

3. Если они равны, верните да, в противном случае нет.

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

Answer 10

Простое и постоянное решение:

return n == power(3, round(log(n) / log(3)))