Jaki jest najprostszy sposób sprawdzenia, czy liczba jest potęgą 2 w C ++?

Potrzebuję takiej funkcji:

// return true iff 'n' is a power of 2, e.g.
// is_power_of_2(16) => true  is_power_of_2(3) => false
bool is_power_of_2(int n);

Czy ktoś może podpowiedzieć, jak mógłbym to napisać? Czy możesz mi podać dobrą stronę internetową, na której można znaleźć tego rodzaju algorytm?

(n & (n - 1)) == 0jest najlepszy. Pamiętaj jednak, że niepoprawnie zwróci wartość true dla n = 0, więc jeśli jest to możliwe, będziesz chciał sprawdzić to jawnie.

http://www.graphics.stanford.edu/~seander/bithacks.html zawiera dużą kolekcję sprytnych algorytmów służących do manipulowania bitami, w tym ten.

Potęga dwójki będzie miała tylko jeden zestaw bitów (dla liczb bez znaku). Coś jak

bool powerOfTwo = !(x == 0) && !(x & (x - 1));

Będzie działać dobrze; jeden mniejszy niż potęga dwóch to wszystkie jedynki w mniej znaczących bitach, więc musi być AND do 0 bitowo.

Ponieważ zakładałem liczby bez znaku, test == 0 (o którym pierwotnie zapomniałem, przepraszam) jest wystarczający. Jeśli używasz liczb całkowitych ze znakiem, możesz potrzebować testu> 0.

Potęgi dwójki w systemie binarnym wyglądają następująco:

1: 0001
2: 0010
4: 0100
8: 1000

Zauważ, że zawsze jest ustawiony dokładnie 1 bit. Jedynym wyjątkiem jest liczba całkowita ze znakiem. Na przykład 8-bitowa liczba całkowita ze znakiem o wartości -128 wygląda następująco:

10000000

Więc po sprawdzeniu, że liczba jest większa od zera, możemy użyć sprytnego małego hackowania, aby sprawdzić, czy ustawiony jest jeden i tylko jeden bit.

bool is_power_of_2(int x) {
    return x > 0 && !(x & (x−1));
}

Więcej informacji na ten temat znajdziesz tutaj .

Podejście nr 1:

Podziel liczbę przez 2, aby to sprawdzić.

Złożoność czasowa: O (log2n).

Podejście nr 2:

Bitowo ORAZ liczba z jej poprzednią liczbą powinna być równa ZERO.

Przykład: Liczba = 8 Binarne liczby 8: 1 0 0 0 Binarne liczby 7: 0 1 1 1, a bitowe AND obu liczb wynosi 0 0 0 0 = 0.

Złożoność czasowa: O (1).

Podejście nr 3:

Bitowy XOR liczba z jej poprzednią liczbą powinna być sumą obu liczb.

Przykład: Liczba = 8 Binarne liczby 8: 1 0 0 0 Binarne liczby 7: 0 1 1 1, a bitowy XOR obu liczb wynosi 1 1 1 1 = 15.

Złożoność czasowa: O (1).

http://javaexplorer03.blogspot.in/2016/01/how-to-check-number-is-power-of-two.html

bool is_power_of_2(int i) {
    if ( i <= 0 ) {
        return 0;
    }
    return ! (i & (i-1));
}

dla każdej potęgi 2 obowiązuje również.

n & (- n) == n

UWAGA: Warunek jest prawdziwy dla n = 0, chociaż nie jest to potęga 2.
Powód, dla którego to działa, jest następujący:
-n jest dopełnieniem 2 do n. -n będzie miał każdy bit na lewo od ustawionego najbardziej na prawo bitu n odwróconego w porównaniu do n. Dla potęgi 2 jest tylko jeden ustawiony bit.

Jest to prawdopodobnie najszybsze, jeśli używasz GCC. Używa tylko instrukcji POPCNT cpu i jednego porównania. Binarna reprezentacja dowolnej potęgi liczby 2, ma zawsze ustawiony tylko jeden bit, pozostałe bity są zawsze równe zero. Więc liczymy liczbę ustawionych bitów za pomocą POPCNT, a jeśli jest równa 1, liczba jest potęgą 2. Nie sądzę, aby istniała szybsza metoda. I to jest bardzo proste, jeśli raz to zrozumiałeś:

if(1==__builtin_popcount(n))

W C ++ 20 jest std::ispow2coś, czego możesz użyć dokładnie do tego celu, jeśli nie musisz go implementować samodzielnie:

#include <bit>
static_assert(std::ispow2(16));
static_assert(!std::ispow2(15));

Następujące odpowiedzi byłyby szybsze niż większość pozytywnych odpowiedzi ze względu na logiczne zwarcie i fakt, że porównanie jest powolne.

int isPowerOfTwo(unsigned int x)
{
  return x && !(x & (x – 1));
}

Jeśli wiesz, że x nie może być 0 to

int isPowerOfTwo(unsigned int x)
{
  return !(x & (x – 1));
}

return n > 0 && 0 == (1 << 30) % n;

Jaki jest najprostszy sposób sprawdzenia, czy liczba jest potęgą 2 w C ++?

Jeśli masz nowoczesny procesor Intel z instrukcjami manipulacji bitami , możesz wykonać następujące czynności. Pomija prosty kod C / C ++, ponieważ inni już na niego odpowiedzieli, ale potrzebujesz go, jeśli BMI nie jest dostępny lub włączony.

bool IsPowerOf2_32(uint32_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u32(x));
#endif
    // Fallback to C/C++ code
}

bool IsPowerOf2_64(uint64_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u64(x));
#endif
    // Fallback to C/C++ code
}

Obsługa BMI sygnałów GCC, ICC i Clang z __BMI__. Jest dostępny w kompilatorach Microsoft w programie Visual Studio 2015 i nowszych, gdy AVX2 jest dostępny i włączony . Aby uzyskać potrzebne nagłówki, zobacz Pliki nagłówkowe dla elementów wewnętrznych SIMD .

Zwykle chronię _blsr_u64to _LP64_w przypadku kompilacji na i686. Clang wymaga małego obejścia, ponieważ używa nieco innej wewnętrznej nazwy symbolu:

#if defined(__GNUC__) && defined(__BMI__)
# if defined(__clang__)
#  ifndef _tzcnt_u32
#   define _tzcnt_u32(x) __tzcnt_u32(x)
#  endif
#  ifndef _blsr_u32
#    define  _blsr_u32(x)  __blsr_u32(x)
#  endif
#  ifdef __x86_64__
#   ifndef _tzcnt_u64
#    define _tzcnt_u64(x) __tzcnt_u64(x)
#   endif
#   ifndef _blsr_u64
#     define  _blsr_u64(x)  __blsr_u64(x)
#   endif
#  endif  // x86_64
# endif  // Clang
#endif  // GNUC and BMI

Czy możesz mi podać dobrą stronę internetową, na której można znaleźć tego rodzaju algorytm?

Ta strona jest często cytowana: Bit Twiddling Hacks .

To nie jest najszybsza ani najkrótsza droga, ale myślę, że jest bardzo czytelna. Więc zrobiłbym coś takiego:

bool is_power_of_2(int n)
  int bitCounter=0;
  while(n) {
    if ((n & 1) == 1) {
      ++bitCounter;
    }
    n >>= 1;
  }
  return (bitCounter == 1);
}

To działa, ponieważ binarny jest oparty na potęgach dwóch. Każda liczba z ustawionym tylko jednym bitem musi być potęgą dwóch.

Oto inna metoda, w tym przypadku za pomocą |zamiast &:

bool is_power_of_2(int x) {
    return x > 0 && (x<<1 == (x|(x-1)) +1));
}

Jest to możliwe dzięki c ++

int IsPowOf2(int z) {
double x=log2(z);
int y=x;
if (x==(double)y)
return 1;
else
return 0;
}

Wiem, że to bardzo stary post, ale pomyślałem, że może być ciekawie zamieścić go tutaj.

Od Code-Golf SE (więc wszystkie zasługi dla autora (ów)): Showcase of Languages

(Akapit o C , długość akapitu 36 fragment )

bool isPow2(const unsigned int num){return!!num&!(num&(num-1));}

Innym sposobem (może nie najszybszym) jest określenie, czy ln (x) / ln (2) jest liczbą całkowitą.

Oto metoda przesunięcia bitów w T-SQL (SQL Server):

SELECT CASE WHEN @X>0 AND (@X) & (@X-1)=0 THEN 1 ELSE 0 END AS IsPowerOfTwo

Jest to o wiele szybsze niż czterokrotne wykonanie logarytmu (pierwszy zestaw, aby uzyskać wynik dziesiętny, drugi zestaw, aby uzyskać liczbę całkowitą, ustaw i porównaj)