Какой самый простой способ проверить, является ли число степенью 2 в C ++?

Question

Мне нужна такая функция:

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

Кто-нибудь может подсказать, как я мог написать это? Можете ли вы сказать мне хороший веб-сайт, где можно найти такой алгоритм?

Answer 1

Это не самый быстрый или самый короткий способ, но я думаю, что он очень удобочитаемый. Поэтому я бы сделал что-то вроде этого:

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

Это работает, поскольку двоичный файл основан на степенях двойки. Любое число, для которого установлен только один бит, должно быть степенью двойки.

Answer 2

В C ++ 20 есть std::ispow2, который вы можете использовать именно для этой цели, если вам не нужно реализовывать его самостоятельно:

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

Answer 3

можно через с ++

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

Answer 4

Вот еще один метод, в данном случае использующий | вместо &:

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

Answer 5

Это метод сдвига битов в T-SQL (SQL Server):

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

Это намного быстрее, чем делать логарифм четыре раза (первый набор для получения десятичного результата, второй набор для получения целого числа и сравнения)

Answer 6

Другой способ (возможно, не самый быстрый) - определить, является ли ln (x) / ln (2) целым числом.