Положение младшего значащего бита, который установлен

Question

Я ищу эффективный способ определения позиции младшего значащего бита, который установлен в целое число, например для 0x0FF0 это будет 4.

Тривиальная реализация такова:

unsigned GetLowestBitPos(unsigned value)
{
   assert(value != 0); // handled separately

   unsigned pos = 0;
   while (!(value & 1))
   {
      value >>= 1;
      ++pos;
   }
   return pos;
}

Есть идеи, как выжать из него несколько циклов?

(Примечание: этот вопрос для людей, которым нравятся такие вещи, а не для людей, которые говорят мне, что ксизоптимизация - это зло.)

[редактировать] Спасибо всем за идеи! Я также узнал несколько других вещей. Круто!

Answer 1

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

Логика просто "value & -value", предположим, что у вас есть 0x0FF0, тогда 0FF0 & (F00F + 1), что равно 0x0010, что означает, что младший 1 находится в 4-м бите ..:)

Answer 2

Если у вас есть ресурсы , вы можете пожертвовать памятью для повышения скорости:

static const unsigned bitPositions[MAX_INT] = { 0, 0, 1, 0, 2, /* ... */ };

unsigned GetLowestBitPos(unsigned value)
{
    assert(value != 0); // handled separately
    return bitPositions[value];
}

Примечание: Эта таблица будет использовать не менее 4 ГБ (16 ГБ, если мы оставим тип возврата как unsigned). Это пример обмена одного ограниченного ресурса (ОЗУ) на другой (скорость выполнения).

Если ваша функция должна оставаться переносимой и работать как можно быстрее любой ценой, это будет путь. В большинстве реальных приложений таблица 4 ГБ нереальна.