Нахождение конечных 0 в двоичном числе

Question

Как найти число конечных нулей в двоичном числе? На основе примера K & R bitcount по нахождению 1с в двоичном числе я немного изменил его, чтобы найти конечные 0.рассмотреть этот метод.

Answer 1

Вот способ вычисления количества параллельно для повышения эффективности:

unsigned int v;      // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;

Answer 2

На GCC на платформе X86 вы можете использовать __builtin_ctz(no) На компиляторах Microsoft для X86 вы можете использовать _BitScanForward

Они оба выдают инструкцию bsf

Answer 3

Другой подход (я удивлен, что он здесь не упоминается) состоит в создании таблицы из 256 целых чисел, где каждый элемент в массиве является младшим 1 битом для этого индекса. Затем для каждого байта в целом числе вы смотрите вверх в таблице.

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

int bitcount(unsigned x)
{
   static const unsigned char table[256] = { /* TODO: populate with constants */ };

   for (int i=0; i<sizeof(x); ++i, x >>= 8)
   {
      unsigned char r = table[x & 0xff];

      if (r)
         return r + i*8;    // Found a 1...
   }

   // All zeroes...
   return sizeof(x)*8;
}

Идея некоторых табличных подходов к такой проблеме заключается в том, что операторы if чего-то стоят с точки зрения прогнозирования ветвлений, поэтому вам следует стремиться к их уменьшению. Это также уменьшает количество битовых сдвигов. Ваш подход делает оператор if и смещение на бит, а этот - один на байт. (Надеюсь, оптимизатор может развернуть цикл for и не запускать сравнение / переход для этого.) Некоторые из других ответов имеют даже меньше операторов if, чем этот, но табличный подход прост и понятен. Конечно, вы должны руководствоваться фактическими измерениями, чтобы выяснить, имеет ли это значение.

Answer 4

int countTrailZero(unsigned x) {
    if (x == 0) return DEFAULT_VALUE_YOU_NEED;
    return log2 (x & -x);  
}

Объяснение:

x & -x возвращает номер самого правого бита, установленного в 1.

например. 6 -> «0000,0110», (6 и -6) -> «0000,0010»

Вы можете вычесть это двумя дополнениями: x = "a1b", где b представляет все завершающие нули. тогда

-x = !(x) + 1 = !(a1b) + 1 = (!a)0(!b) + 1 = (!a)0(1...1) + 1 = (!a)1(0...0) = (!a)1b 

так

x & (-x) = (a1b) & (!a)1b = (0...0)1(0...0)

Вы можете получить число конечных нулей, просто выполнив log2.

Answer 5

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

int bitcount(unsigned x) {
    int xor = x ^ (x-1); // this will have (1 + #trailing 0s) trailing 1s
    return log(i & xor); // i & xor will have only one bit 1 and its log should give the exact number of zeroes
}

Answer 6

У меня есть быстрая и эффективная функция:

int bitcount(unsigned __int64 value)
{
    if (!value)
        return SOME_DEFAULT_VALUE;

    value &= -value;
    unsigned int lsb = (unsigned) value | (unsigned) (value >> 32);
    return (int)(((((((((((unsigned) (value >> 32) != 0) * 2)
            + ((lsb & 0xffff0000) != 0)) * 2)
            + ((lsb & 0xff00ff00) != 0)) * 2)
            + ((lsb & 0xf0f0f0f0) != 0)) * 2)
            + ((lsb & 0xcccccccc) != 0)) * 2)
            + ((lsb & 0xaaaaaaaa) != 0);
}

но будьте осторожны, как вы видите, есть 2 проблемы с этим:

1. Эта функция определена для 64-битных целых чисел. (вы можете использовать его для кастинга)
2. Для значения 0 необходимо определить значение по умолчанию. (например, 0 или -1)

я думаю, что эти проблемы терпимы с некоторой осторожностью.

Answer 7

Я думаю, ваш метод работает (хотя вы можете использовать unsigned int).Вы проверяете последнюю цифру каждый раз, и, если она равна нулю, вы сбрасываете ее, увеличивая число конечных нулевых битов.

Я думаю, что для конечных нулей вам не нужен цикл.

Рассмотрим следующее:

• Что происходит с числом (в двоичном представлении, конечно), если вы вычесть 1?Какие цифры меняются и остаются неизменными?
• Как можно объединить исходное число и уменьшенную версию так, чтобы остались только биты, представляющие завершающие нули?

Если применить вышеизложенноешаги правильно, вы можете просто найти старший бит, установленный в O (lg n) шагах (смотрите здесь , если вы заинтересованы в том, как это сделать).

Answer 8

Должно быть:

int bitcount(unsigned char x)
{
  int b;
  for(b=0; b<7; x>>=1)
  {
    if(x&1)
      break;
    else
      b++;
  }
  return b;
}

или даже

int bitcount(unsigned char x)
{
  int b;
  for(b=0; b<7 && !(x&1); x>>=1) b++;
  return b;
}

или даже (ууу!)

int bitcount(unsigned char x)
{
  int b;
  for(b=0; b<7 && !(x&1); b++) x>>=1;
  return b;
}

или ...

Ах, как бы там ни было, Есть 100500 миллионов способов сделать это .Используйте все, что вам нужно или нравится.