Есть ли простой способ узнать, какая из двух степеней является числом?

Question

Если у меня есть число, которое, как я уверен, является степенью двойки, есть ли способ узнать, какой степенью двойки является число? Я думал об этой идее: Имея счет и смещая число вправо на 1 и увеличивая счет до тех пор, пока число не станет 0. Однако есть ли другой способ? Не ведя счетчик?

Edit: Вот некоторые примеры: 8 -> возвращает 3 16 -> возвращает 4 32 -> возвращает 5

Answer 1

Самый элегантный метод - последовательности де Брюина.Вот предыдущий ответ, который я дал на аналогичный вопрос о том, как использовать их для решения проблемы:

Перестановка битов: какой бит установлен?

Часто более-практический подход использует встроенную инструкцию вашего процессора для поиска первого / последнего установленного бита.

Answer 2

Если это число называется x, вы можете найти его, вычислив log2f(x).Возвращаемое значение - это число с плавающей запятой.

Вам нужно будет включить <math.h>, чтобы использовать log2f.

Answer 3

Этот метод, безусловно, будет работать. Другим возможным способом было бы исключить половину возможностей каждый раз. Допустим, у вас есть 8-битное число: 00010000

Побитово и ваше число, где половина битов равна единице, а другая половина равна нулю, скажем, 00001111.

00010000 & 00001111 = 00000000

Теперь вы знаете, что это не первые четыре бита. Делайте это несколько раз, пока не получите 0:

00010000 и 00110000 = 00010000

А затем сузьте его до одного возможного бита, равного 1, который является вашей степенью двойки.

Answer 4

Использовать бинарный поиск вместо линейного:

public void binarySearch() throws Exception {
  int num = 0x40000;

  int k = 0;
  int shift = 16; // half of the size of the type (for in 16, etc)
  int a = 0xffff; // lower half should be f's

  while (shift != 0) {
    if ((num & a) == 0) {
      num = num >>> shift;
      k += shift;
      shift >>= 1;
    } else {
      shift >>= 1;
    }
    a = a >>> shift;
  }
  System.out.println(k);
}

Answer 5

Вы можете использовать функцию log в cmath ...

double exponent = log(number)/log(2.0);

... и затем привести ее к int.