Сложная временная сложность

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)unsets the rightmost set bit.

Продолжительность 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

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

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

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

Answer 5

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