Задача на C#. Как мне найти степень числа(без Math.Pow)?

Question

[stividjon]

int a = 2;
int result = 64;

Мне нужно найти степень числа 2(int a) чтобы по результату(result) было верно. Т.е. консоль должен вывести число 6. Только реализовать эту программу нужно без Math.Pow

Comments

[alexalexes]

..., наверное, и без Math.Log тоже? Вы ведь эту функцию будете реализовывать?

А result вам точно будут всегда предлагать 2^n ? Не может быть 65, или 127?
Не ясно, какого типа должен быть результат? Вы точно целочисленный ожидаете?
А если не целочисленный, то какой точности он нужен? В какую сторону округлять?
Даже если целочисленный, какая степень округления нужна - в большую или меньшую сторону (это про вариант 65, или 127 )?
Для целочисленных результатов вы можете воспользоваться простым перебором степеней, либо оптимизировать поиск степени методом бинарного поиска.
Для вещественных результатов (общего решения задачи в вещественных числах) нужно ознакомиться с целой статьей "Дискретное логарифмирование".

Answer 1

[Александр Ананьев]

Просто напишу код целочисленного логарифма по основанию 2, может кому пригодится

using System;
class Log2Test {
  static uint pop(uint x)
  {
      uint n;
      n = (x >> 1) & 0x77777777;
      x = x - n;
      n = (n >> 1) & 0x77777777;
      x = x - n;
      n = (n >> 1) & 0x77777777;
      x = x - n;
      x = (x + (x >> 4)) & 0x0f0f0f0f;
      x = x * 0x01010101;
      return x >> 24;
  }
  static uint log2(uint x)
  {
      x = x | (x >> 1);
      x = x | (x >> 2);
      x = x | (x >> 4);
      x = x | (x >> 8);
      x = x | (x >> 16);
      return pop(x)-1;
  }
  static void Main() {
    for(int i = 0; i < 31; i++)
    {
        uint x = 2U << i;
        Console.WriteLine("log2({0})={1}", x, log2(x));
    }
  }
}

Answer 2

[stividjon]

int a = 2;
int result = 64;
int power = 0;

while( result != 1 )
{
result /= a;
power++;
}
Console.WriteLine(power);

Comments

[GavriKos]

Стоп. Это не степень. Это корень.

[Василий Банников]

GavriKos, может всётаки логарифм?

[GavriKos]

Василий Банников, ну да, логарифм, согласен. Крч не степень )

Answer 3

[Voland69]

Так как в вопросе Math.Pow использовать запрещено, но о других методах речи не шло, можно определить логарифм по произвольному основанию используя натуральный логарифм и школьную формулу.

int a = 2;
int b = 64;
var result = Math.Log(b) / Math.Log(a);  // 6

Comments

[alexalexes]

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

Answer 4

[Довольный Айтишникъ]

Напишите алгоритм, как бы вы это сделали вручную, а потом переведите его в код.

Answer 5

[GavriKos]

Ну берете математическое определение степени, главу про циклы, и реализуете

Answer 6

[Griboks]

Умножение/деление на 2 эквивалентно бинарному сдвигу (>>, <<) на 1. Сколько раз пришлось сдвинуть 64 вправо, чтобы получить 1, таков и ответ.
64 >> 6 = 1 => 2^6=64 <=> 1 << 6 = 64

p.s.
#Программистам не нужна математика.

Answer 7

[WAR_VIK]

Можно так:

int num = 2, n = num, res = 64, pow = 1;
while(num < res) {
  num *= n; ++pow;
}
Console.WriteLine(pow);