program do sprawdzania czy liczba jest potęgą 2 - Sprawdzenie poprawności kodu

Question

Witam 

Mam takie zadanie: Napisz program, który sprawdzi czy podana liczba jest potęgom liczby 2. Napisałem taki program 

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
   int liczba;
   printf("Podaj liczbe: ");
   scanf("%d", &liczba);

   while(liczba % 2 == 0)
   {
       liczba = liczba / 2;
   }
    if(liczba == 1)
    {
        printf("Podana liczba jest potegom 2");
    }
    else
    {
        printf("Podana liczba nie jest potegom 2");
    }

    return (0);
}

Program działa jak należy ale chciałem się upewnić czy aby napewno jest to zrobione jak należy czy można to zrobić inaczej lepiej?. Prosiłbym, żeby ktoś odpowiedział na moje pytanie. Z góry dziękuję.

Answer 1

Złożoność twojego algorytmu to O(log(2)n), da się to zrobić lepiej i szybciej np. w złożoności O(1).

Można to zrobić porównując bity liczby. Zauważ że potęgi dwójki np. 16 mają w zapisie bitowym tylko jedną jedynkę:

10000. Liczba 15 to 01111. Za pomocą operatora & sprawdzisz czy liczby będą miały w jakimś tym samym miejscu jedynki.

Dla 10000 & 01111 = 00000 => 0. Więc wystarczy zwrócić dla jakiejś liczby x:    x && (!(x&(x-1))). Sprawdzamy jeszcze po lewej stronie x żeby sprawdzić czy nie równa się zero.

Comments

dokładnie operacja XOR jest operacją rozwiązująca ten problem