Apa cara paling sederhana untuk menguji apakah suatu bilangan adalah pangkat 2 di C ++?

Saya butuh fungsi seperti ini:

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

Adakah yang bisa menyarankan bagaimana saya bisa menulis ini? Dapatkah Anda memberi tahu saya situs web yang bagus tempat algoritme semacam ini dapat ditemukan?

(n & (n - 1)) == 0paling baik. Namun, perhatikan bahwa ini akan salah mengembalikan nilai true untuk n = 0, jadi jika memungkinkan, Anda ingin memeriksanya secara eksplisit.

http://www.graphics.stanford.edu/~seander/bithacks.html memiliki banyak koleksi algoritme bit-twiddling yang cerdas, termasuk yang ini.

Sebuah kekuatan dua hanya akan memiliki satu set bit (untuk nomor yang tidak bertanda tangan). Sesuatu seperti

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

Akan bekerja dengan baik; satu kurang dari pangkat dua adalah semua 1 dalam bit kurang signifikan, jadi harus DAN 0 bitwise.

Karena saya mengasumsikan angka yang tidak ditandatangani, tes == 0 (yang awalnya saya lupa, maaf) sudah memadai. Anda mungkin menginginkan tes> 0 jika Anda menggunakan bilangan bulat bertanda.

Pangkat dua dalam biner terlihat seperti ini:

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

Perhatikan bahwa selalu ada 1 bit set. Satu-satunya pengecualian adalah dengan bilangan bulat yang ditandatangani. Misalnya, bilangan bulat bertanda 8-bit dengan nilai -128 terlihat seperti ini:

10000000

Jadi setelah memeriksa bahwa angkanya lebih besar dari nol, kita dapat menggunakan sedikit retasan pintar untuk menguji bahwa satu dan hanya satu bit yang ditetapkan.

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

Untuk sedikit bermain-main, lihat di sini .

Pendekatan # 1:

Bagilah angka dengan 2 secara berturut-turut untuk memeriksanya.

Kompleksitas waktu: O (log2n).

Pendekatan # 2:

Bitwise AND angka dengan angka sebelumnya harus sama dengan NOL.

Contoh: Angka = 8 Biner 8: 1 0 0 0 Biner 7: 0 1 1 1 dan bitwise AND dari kedua bilangan tersebut adalah 0 0 0 0 = 0.

Kompleksitas waktu: O (1).

Pendekatan # 3:

Bitwise XOR angka dengan angka sebelumnya harus merupakan jumlah dari kedua angka.

Contoh: Bilangan = 8 Biner 8: 1 0 0 0 Biner 7: 0 1 1 1 dan XOR bitwise dari kedua bilangan tersebut adalah 1 1 1 1 = 15.

Kompleksitas waktu: 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));
}

untuk pangkat 2 apa pun, berikut ini juga berlaku.

n & (- n) == n

CATATAN: Kondisi ini benar untuk n = 0, meskipun itu bukan pangkat 2.
Alasan mengapa ini berhasil adalah:
-n adalah komplemen 2s dari n. -n akan memiliki setiap bit di sebelah kiri set bit paling kanan dari n dibalik dibandingkan dengan n. Untuk pangkat 2 hanya ada satu set bit.

Ini mungkin yang tercepat, jika menggunakan GCC. Ini hanya menggunakan instruksi cpu POPCNT dan satu perbandingan. Representasi biner dari setiap pangkat 2 angka, selalu hanya satu set bit, bit lain selalu nol. Jadi kami menghitung jumlah bit set dengan POPCNT, dan jika itu sama dengan 1, jumlahnya adalah pangkat 2. Saya rasa tidak ada metode yang lebih cepat. Dan itu sangat sederhana, jika Anda memahaminya sekali:

if(1==__builtin_popcount(n))

Di C ++ 20 ada std::ispow2yang dapat Anda gunakan untuk tujuan ini jika Anda tidak perlu mengimplementasikannya sendiri:

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

Mengikuti akan lebih cepat daripada jawaban yang paling banyak dipilih karena hubungan pendek boolean dan fakta bahwa perbandingannya lambat.

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

Jika Anda tahu bahwa x tidak bisa 0 maka

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

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

Apa cara paling sederhana untuk menguji apakah suatu bilangan adalah pangkat 2 di C ++?

Jika Anda memiliki prosesor Intel modern dengan Petunjuk Manipulasi Bit , Anda dapat melakukan hal berikut. Ini menghilangkan kode C / C ++ langsung karena orang lain telah menjawabnya, tetapi Anda memerlukannya jika BMI tidak tersedia atau diaktifkan.

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
}

GCC, ICC, dan Clang memberi sinyal dukungan BMI dengan __BMI__. Ini tersedia di kompiler Microsoft di Visual Studio 2015 dan di atasnya saat AVX2 tersedia dan diaktifkan . Untuk header yang Anda perlukan, lihat File header untuk intrinsik SIMD .

Saya biasanya menjaga _blsr_u64dengan _LP64_jika kompilasi pada i686. Clang memerlukan sedikit solusi karena menggunakan simbol intrinsik nam yang sedikit berbeda:

#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

Dapatkah Anda memberi tahu saya situs web yang bagus di mana algoritme semacam ini dapat ditemukan?

Situs web ini sering dikutip: Bit Twiddling Hacks .

Ini bukan cara tercepat atau terpendek, tapi menurut saya ini sangat mudah dibaca. Jadi saya akan melakukan sesuatu seperti ini:

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

Ini berfungsi karena biner didasarkan pada pangkat dua. Setiap angka dengan hanya satu set bit harus menjadi pangkat dua.

Berikut adalah metode lain, dalam hal ini menggunakan |sebagai pengganti &:

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

Ini dimungkinkan melalui c ++

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

Saya tahu ini adalah posting yang sangat lama, tetapi saya pikir akan menarik untuk memposting ini di sini.

Dari Code-Golf SE (jadi semua kredit kepada orang-orang yang menulis ini): Showcase of Languages

(Paragraph about C , subparagraph Length 36 snippet )

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

Cara lain untuk pergi (mungkin bukan tercepat) adalah dengan menentukan apakah ln (x) / ln (2) adalah bilangan bulat.

Ini adalah metode bit-shift di T-SQL (SQL Server):

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

Ini jauh lebih cepat daripada melakukan logaritma empat kali (set pertama untuk mendapatkan hasil desimal, set kedua untuk mendapatkan set integer & bandingkan)