Уменьшение сложности времени

Question

int main()
{
   int n ;
   std::cin >> n; // or scanf ("%d", &n);
   int temp;
   if( n ==1 ) temp = 1; // if n is 1 number is power of 2 so temp = 1
   if( n % 2 != 0 && n!= 1) temp =0; // if n is odd it can't be power of two
   else
   {
       for (;n && n%2 == 0; n /= 2);
       if(n  > 0 && n!= 1) temp = 0; // if the loop breaks out because of the second condition
       else temp = 1;
   }

   std::cout << temp; // or printf ("%d", temp);
}

Приведенный выше код проверяет, является ли число степенью двойки.В наихудшем случае сложность времени выполнения - O (n).Как оптимизировать код, сократив временную сложность?

Answer 1

Попробуйте if( n && (n & (n-1)) == 0) temp = 1; проверить, является ли число степенью двойки или нет.

Например:

n = 16;

  1 0 0 0 0 (n)
& 0 1 1 1 1 (n - 1)
  _________
  0 0 0 0 0 (yes)

Число, котороеэто мощность 2 имеет только один установленный бит.

n & (n - 1) сбрасывает самый правый установленный бит .

Время работы O(1); -)

Как заметил @ GMan , n должно быть целым числом без знака.Побитовая операция с отрицательными знаковыми целыми числами определяется реализацией.

Answer 2

Как насчет этого?

bool IsPowerOfTwo(int value)
{
    return (value && ((value & (value-1)) == 0);
}

Answer 3

попробуйте это: bool isPowerOfTwo = n && !(n & (n - 1));

Answer 4

bool ifpower(int n)
{
    if(log2(n)==ceil(log2(n))) return true;
    else return false;
}

Answer 5

Вместо деления числа на 2, вы можете сдвинуть его вправо на 1. Это универсальное правило оптимизации для деления на 2,4,8,16,32 и так далее. Это деление можно заменить на сдвиг вправо 1,2,3,4,5 и так далее. Они математически эквивалентны.

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

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