it-swarm-eu.dev

Jaký je nejjednodušší způsob, jak otestovat, zda je číslo v C++ mocninou 2?

Potřebuju takovou funkci:

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

Může někdo navrhnout, jak bych to mohl napsat? Můžete mi říct, dobré webové stránky, kde tento druh algoritmu lze nalézt?

72
Ant

(n & (n - 1)) == 0 je nejlepší. Všimněte si však, že nesprávně vrátí hodnotu true pro n = 0, takže pokud je to možné, budete jej chtít explicitně zkontrolovat.

http://www.graphics.stanford.edu/~seander/bithacks.html má velkou sbírku chytrých bit-twiddling algoritmů, včetně tohoto.

156
Anonymous

Síla dvou bude mít pouze jeden bit nastavený (pro nepodepsaná čísla). Něco jako

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

Bude fungovat dobře; jedna menší než síla dvou je všech 1 v méně významných bitech, takže musí být A až 0 bitové.

Jelikož jsem předpokládal nepodepsaná čísla, test == 0 (který jsem původně zapomněl, omlouvám se) je adekvátní. Pokud používáte podepsaná celá čísla, můžete chtít test> 0.

72
Adam Wright

Pravomoci dvou v binárním provedení vypadají takto:

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

Všimněte si, že je vždy přesně nastaven 1 bit. Jedinou výjimkou je podepsané celé číslo. např. 8bitové celé číslo s hodnotou -128 vypadá takto:

10000000

Takže po kontrole, že číslo je větší než nula, můžeme použít chytrý trochu hack testovat, že jeden a jediný bit je nastaven.

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

Pro více bitů viz zde .

44
Matt Howells

Přístup č. 1:

Rozdělte číslo podle počtu 2, abyste ho zkontrolovali.

Časová složitost: O (log2n).

Přístup č. 2:

Bitové A číslo s jeho předcházejícím číslem by mělo být rovno ZERO.

Příklad: Číslo = 8 Binární hodnota 8: 1 0 0 0 Binární hodnota 7: 0 1 1 1 a bitová A obou čísel je 0 0 0 0 = 0.

Časová složitost: O (1).

Přístup č. 3:

Bitové XOR číslo s jeho předcházejícím číslem by mělo být součtem obou čísel.

Příklad: Číslo = 8 Binární hodnota 8: 1 0 0 0 Binární hodnota 7: 0 1 1 1 a bitová hodnota XOR obou čísel je 1 1 1 1 = 15.

Časová složitost: O (1).

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

12
Raj Dixit
bool is_power_of_2(int i) {
    if ( i <= 0 ) {
        return 0;
    }
    return ! (i & (i-1));
}
5
Rob Wells

pro každý výkon 2 platí také následující.

n & (- n) == n

Poznámka: Podmínka platí pro n = 0, i když není mocnina 2.
Důvod, proč je tato práce: 
- n je 2s doplněk n. -n bude mít každý bit vlevo od nastaveného bitu n nejvíce převráceného oproti n. Pro výkony 2 je pouze jeden nastavený bit.

3
FReeze FRancis
return n > 0 && 0 == (1 << 30) % n;
3
Yuxiang Zhang

Jaký je nejjednodušší způsob, jak otestovat, zda je číslo v C++ mocninou 2?

Pokud máte moderní procesor Intel s Bit Manipulation Instructions , pak můžete provést následující. Vynechá rovný kód C/C++, protože ostatní již na něj odpověděli, ale potřebujete jej, pokud není služba BMI dostupná nebo povolena.

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
}

Podpora GCC, ICC a signalizace signalizace BMI s __BMI__. Je k dispozici v kompilátorech Microsoftu v aplikaci Visual Studio 2015 a vyšší, když je k dispozici AVX2 a je povoleno . Pro záhlaví, které potřebujete, viz Soubory záhlaví pro vnitřní vlastnosti SIMD .

Obvykle hlídám _blsr_u64 s _LP64_ v případě kompilace na i686. Clang potřebuje malé řešení, protože používá mírně odlišný vnitřní symbol nam:

#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

Můžete mi říct, dobré webové stránky, kde tento druh algoritmu lze nalézt?

Tento web je často citován: Bit Twiddling Hacks .

2
jww

Následování by bylo rychlejší než většina hlasů, které jsou odhlasovány z důvodu booleovského zkratu a skutečnosti, že srovnání je pomalé.

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

Pokud víte, že x nemůže být 0, pak 

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

To není nejrychlejší nebo nejkratší cesta, ale myslím, že je to velmi čitelné. Tak bych udělal něco takového:

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

Toto funguje, protože binární systém je založen na schopnostech dvou. Každé číslo s nastaveným jedním bitem musí být mocninou dvou.

1
Jere.Jones

Toto je nejrychlejší:

if(1==__builtin_popcount(n))
1
F10PPY

Zde je další metoda, v tomto případě použití | namísto &:

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

Je možné přes c ++

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