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


95

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?



@rootTraveller - prawdopodobnie nie jest to duplikat. C ++ i Java to różne języki i każdy z nich oferuje inne udogodnienia. Na przykład w C / C ++ możemy teraz używać elementów wewnętrznych z procesorami obsługującymi BMI, które wydają instrukcje maszynowe, aby zrobić to w jednym zegarze. Wyobrażam sobie, że Java ma inne rzeczy, na przykład coś z procedury matematycznej.
jww

Odpowiedzi:


192

(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.


8
czyli w zasadzie(n>0 && ((n & (n-1)) == 0))
Saurabh Goyal

1
@SaurabhGoyal lub n && !(n & (n - 1))jak podaje link w odpowiedzi.
Carsten

Dlaczego, och dlaczego, nie znajduje się to na początku odpowiedzi? OP proszę przyjąć.
donturner

@SaurabhGoyal Jedna mała poprawa jest taka: n & !(n & (n - 1)). Zwróć uwagę na bitowe AND &(nie logiczne i &&). Operatory bitowe nie implementują zwarcia, a zatem kod nie rozgałęzia się. Jest to preferowane w sytuacjach, w których prawdopodobne jest błędne przewidywanie gałęzi i gdy obliczanie prawej strony wyrażenia (to znaczy !(n & (n - 1))) jest tanie.
Cassio Neri

@cassio !jest operatorem logicznym i dlatego wartość !(n & (n - 1))byłaby wartością logiczną. Czy na pewno operatorowi bitowemu AND można podać wartość logiczną i liczbę? Jeśli tak, to wygląda dobrze.
Saurabh Goyal

81

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.


Brakuje znaku „!” lub „== 0”

Brakuje Ci również testu na ujemną wartość x.
Rob Wells

Świetnie, jak go wyedytowałeś bez pojawienia się „edytowano x minut temu”?

Poważnie, jak udało ci się uzyskać 120 powtórzeń za ewidentnie błędną odpowiedź?

@Mike F: Rzeczywiście, wygląda na to, że ludzie będą głosować na odpowiedzi bez ich sprawdzania. Myślę, że każdy może popełnić błąd - jeśli popełnię jakiś błąd w przyszłości, nie krępuj się go usunąć.
Adam Wright,

49

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 .


14

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


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

7

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.



Czy to działa z konwersjami, które mają miejsce, jeśli n jest bez znaku?
Joseph Garvin

6

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))

Nie. Właśnie to przetestowałem. Uwielbiam popcount, ale w przypadku testu power-of-2 test i && !(i & (i - 1)))jest około 10% szybszy na moim komputerze, nawet jeśli byłem pewien, że włączam natywną instrukcję POPCNT zestawu w gcc.
eraoul

Ups, cofam to. Mój program testowy działał w pętli, a przewidywanie gałęzi było „oszukiwaniem”. Masz rację, jeśli masz instrukcję POPCNT na swoim procesorze, jest szybsza.
eraoul

5

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));

3

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));
}


3

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 .


Z pewnością nie jest to „najprostszy sposób”, jak żądano w PO, ale prawdopodobnie najszybszy dla określonych środowisk. Pokazanie, jak uwarunkować dla różnych architektur, jest niezwykle przydatne.
Fearless_fool

1

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.


Może nie jest szybkie ani krótkie, ale jest poprawne w przeciwieństwie do najlepszych odpowiedzi.

2
W momencie komentowania wszystkie były podsłuchiwane. Od tego czasu zostały zredagowane do akceptowalnego stanu.

0

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));
}

0

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;
}

2
Nie jest to dla mnie ani proste, ani szybkie.
luk32

2
Tzn. Z pewnością nie jest to szybkie ze względu na log2, a dowód na to, że działa, nie jest tak łatwy do wyjaśnienia (dokładnie, czy można dać się złapać na błędach zaokrągleń?). Jest też niepotrzebnie zagmatwany if..return..else..return. Co jest złego w zwinięciu go do return x==(double)y;? Powinien zwrócić boolAnyayws. IMO nawet operator trójskładnikowy byłby jaśniejszy, gdyby ktoś naprawdę chciał się trzymać int.
luk32

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));}

-1

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


2
Nie ma chyba o tym :-).
paxdiablo

1
Mogłoby to powodować problemy z niedokładnością zmiennoprzecinkową. ln (1 << 29) / ln (2) wychodzi na 29.000000000000004.
Anonimowy

-3

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)


5
Dobrze jest zobaczyć, jak najlepsza odpowiedź na to pytanie może być również zaimplementowana w T-SQL, ale nie jest to tak naprawdę istotne w przypadku zadanego tutaj pytania. Alternatywą (jeśli szukałeś rozwiązania w T-SQL, znalazłeś odpowiedź na to pytanie, zaimplementowałeś je w T-SQL i uznałeś za wystarczająco interesujące, aby opublikować tę odpowiedź) byłoby opublikowanie pytania w odniesieniu do T-SQL odpowiedz samodzielnie, w odniesieniu do odpowiedzi na to pytanie. Mam nadzieję, że ta sugestia jest pomocna.
Simon

to naprawdę nie odpowiada na to pytanie
phuclv
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.