Количество битов, необходимых для представления числа x

Question

В настоящее время я пытаюсь написать алгоритм, который определяет, сколько бит необходимо для представления числа x.Моя реализация будет в ц.Хотя есть несколько уловок, я ограничен в значительной степени только побитовыми операторами {~, &, ^, |, +, <<, >>}.Кроме того, я не могу использовать какой-либо тип потока управления (если, пока, для).Мой первоначальный подход состоял в том, чтобы исследовать число в двоичном виде слева направо и искать, где встречается первое «1».Я не уверен, как подойти к этому, учитывая мои ограничения.Число, с которым я работаю, можно считать целым числом без знака.Таким образом, 00110 потребует только 3 бита.

Мне интересно, есть ли гораздо более простой / чистый способ сделать это, и мне не хватает его?Или, если кто-то может дать несколько подсказок?

По сути, я пытался реализовать это без цикла while:

 int result = 0;
  while (x >>= 1) {
    result += 1;
  }
  return result;

Answer 1

http://www -graphics.stanford.edu / ~ seander / bithacks.html # IntegerLog

Показывает, как это сделать без потока управления.

unsigned int v;          // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;

r =     (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
                                        r |= (v >> 1);
r++;

Answer 2

Пожалуйста, попробуйте:

// http://www.cs.northwestern.edu/~wms128/bits.c
int check_bits_fit_in_2s_complement(signed int x, unsigned int n) {
  int mask = x >> 31;

  return !(((~x & mask) + (x & ~mask))>> (n + ~0));
}

Answer 3

Принятый ответ на самом деле неверен: например, он выдает 5 для 32..63 (вместо 6), 4 для 16..31 (вместо 5).Это все равно что взять логарифм с основанием 2 и округлить вниз.

Правильное решение выглядит следующим образом:

unsigned int v;          // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;

r =     (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
                                        r |= (v >> 1);
r++;

Обратите внимание на r ++ .

Answer 4

У меня есть решение.Это не быстро.Он рассчитывает количество необходимых битов, то есть 32 для 0xFFFFFFFF и 0 для 0x00000000.Обратите внимание, что ваш код C действительно вычисляет старший значащий бит или ноль.

Вот оно:

#define ISSET(x,i) (((x) >> (i)) & 1)
#define FILL(x) (-(x))
#define IF(x,y,z) ((FILL(x) & y) | (~FILL(x) & z))
#define R(x,i,y,z) (IF(ISSET(x,i),y,z))

int log2 (uint32_t x)
{
  return  R(x,31,32,
          R(x,30,31,
          R(x,29,30,
          R(x,28,29,
          R(x,27,28,
          R(x,26,27,
          R(x,25,26,
          R(x,24,25,
          R(x,23,24,
          R(x,22,23,
          R(x,21,22,
          R(x,20,21,
          R(x,19,20,
          R(x,18,19,
          R(x,17,18,
          R(x,16,17,
          R(x,15,16,
          R(x,14,15,
          R(x,13,14,
          R(x,12,13,
          R(x,11,12,
          R(x,10,11,
          R(x, 9,10,
          R(x, 8, 9,
          R(x, 7, 8,
          R(x, 6, 7,
          R(x, 5, 6,
          R(x, 4, 5,
          R(x, 3, 4,
          R(x, 2, 3,
          R(x, 1, 2,
          R(x, 0, 1, 0))))))))))))))))))))))))))))))));
}

Примечание. Общий принцип можно использовать для других функций.

Answer 5

Ну, я думаю, ему нужен счетчик первого бита, а не счетчик последнего бита.Поскольку этот алгоритм подразумевает 32-битное целое число, результат должен быть исправлен.

unsigned int v;          // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;

r =     (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
                                        r |= (v >> 1);
return 32-r;