определить силу числа

Question

я знаю, что если число является степенью двойки, то оно должно удовлетворять (x&(x-1))=0;, например, давайте возьмем x=16 or 10000 x-16=10000-1=01111 и (x & (x-1)) = 0; для другого не степенного числа 7 дляНапример, 7=0111, 7-1=0110 7&(7-1)=0110, который не равен 0, мой вопрос, как я могу определить, является ли число некоторой степенью другого числа k? Например, 625 равно 5 ^ 4, а также как найти, в какоммощность равна k к n? Мне интересно использовать побитовые операторы, конечно, я могу найти его методами грубой силы (по стандартному алгоритму, большое спасибо

Answer 1

Я сомневаюсь, что вы найдете побитовый алгоритм для определения того, что число является степенью 5.

В общем случае, если y = n^x, чтобы найти x, вам нужно использовать логарифмы, т.е. x = log_n(y). Большинство языков не предлагают функцию log_n, но вы можете достичь ее с помощью следующего идентификатора:

log_n(y) = log(y) / log(n)

Если y представляет собой целую степень n, тогда x будет целым числом. Конечно, из-за ограничений компьютерной арифметики конечной точности вы не обязательно получите точный ответ описанным выше методом.

Answer 2

Боюсь, вы не можете сделать это с помощью простой магии.Биты, как правило, хороши для степеней 2. Например, для степеней 5 вам, вероятно, придется работать в системе с базовым уровнем 5, где 1 ₅ = 1 ₁₀ , 10 ₅ = 5 ₁₀ , 100 ₅ = 25 ₁₀ , 1000 ₅ = 125 ₁₀ , 10000 ₅ = 625 ₁₀ и т. Д. В системе base-5 вы можете распознавать степени 5 так же легко, как и степени 2 в двоичной системе.Но сначала вам нужно преобразовать свои числа в эту базу.

Answer 3

Для произвольного k есть только общее решение:

bool is_pow(unsigned long x, unsigned int base) {
  assert(base >= 2);
  if (x == 0) {
    return false;
  }
  unsigned long t = x;
  while (t % base == 0) {
    t /= base;
  }
  return t == 1;
}

Когда k - это степень двух, вы можете ускорить процесс, проверив, является ли x степенью двухи делится ли число завершающих нулевых битов x на log2(k).

И если важна скорость вычислений и ваша k фиксирована, вы всегда можете использовать тривиальную реализацию:

bool is_pow5(unsigned long x) {
  if (x == 5 || x == 25 || x == 125 || x == 625)
    return true;
  if (x < 3125)
    return false;
  // you got the idea
  ...
}