Блог

В нашем классе алгоритмов у профессора на лабораторной сессии возник дополнительный вопрос. Найдите floor(log2(x)) для int из n бит за log2 (n) шага (например, когда T = uint64_t, тогда n = 64).

Мы обнаружили, что должны быть в состоянии решить эту проблему с помощью двоичного поиска, но мы получаем отклонение на 1 результат или бесконечный цикл в определенных крайних случаях. Некоторое время мы ломаем голову, но, похоже, не можем сделать это правильно. Как нам лучше всего с этим справиться? Мы пытались использовать инвариантный трюк, как обсуждалось здесь, но он кажется немного более сложным, чем. Например. для десятичного числа, когда выбор между битами 7 или 6 затруднен, поскольку 128 больше 100, но 64 меньше. К сожалению, при смягчении этого мы нарушаем некоторые крайние случаи.

РЕДАКТИРОВАТЬ: Как отмечено ниже, это чисто академический вопрос с низким или нулевым удобством использования в реальных сценариях.

Вот наш код на данный момент:

 //
//   h      l
//   76543210
// 0b01000001 = 65
//

using T = unsigned char;

int lgfloor(T value)
{
    assert(value > 0);

    int high = ((sizeof(value) * 8) - 1);
    int low = 0;
    int mid = 0;
    T guess = 0;

    while (high > low)
    {
        mid = (low   ((high - low) / 2));
        guess = static_cast<T>(1) << mid;

        printf("high: %d, mid: %d, low: %dn", high, mid, low);

        if (value < guess)
        {
            high = mid - 1;
        }
        else
        {
            low = mid;
        }
    }

    return low;
}
  

Мы создали следующие модульные тесты (используя GoogleTest):

 TEST(LgFloor, lgfloor)
{
    ASSERT_DEATH(lgfloor(-1), "Assertion `value > 0' failed.");
    ASSERT_DEATH(lgfloor(0), "Assertion `value > 0' failed.");

    ASSERT_EQ(lgfloor(1), 0);
    ASSERT_EQ(lgfloor(2), 1);
    ASSERT_EQ(lgfloor(64), 6);
    ASSERT_EQ(lgfloor(100), 6);
}
  

Заранее спасибо,
с наилучшими пожеланиями,

Marten

Вам нужно правильное условие выхода. Допустим y = floor(lg2(x)) . Вы должны выйти из цикла, когда 2^low <= x и x < 2^(low 1) . Но если high == low 1 тогда это выполнено, все же вы в данный момент не завершаете работу. Просто сделайте:

 while (high > low 1)
{
  

Полезно посмотреть на инварианты в вашем цикле. Например, мы могли бы попытаться поддерживать x < 2^high (для этого потребовалось бы начинать с sizeof(T)*8 , а не sizeof(T)*8 - 1 с). Затем все, что вам нужно сделать, это разделить пополам, пока low == high-1 и вы не закончите.

Мы можем сохранить этот инвариант, только изменив high на mid if x < 2^mid , т.е. если value < guess . Это первый случай:

 if (value < guess)
  high = mid;
  

Мы далее должны поддерживать 2^low <= x = value . Итак, в ветке else (которая требует 2^mid == guess < value , мы можем безопасно установить low = mid .

 else
  low = mid;
  

Все, что осталось, это доказать, что цикл всегда выполняется. Поскольку high > low 1 , мы имеем high - low >= 2 и, следовательно, mid != low и mid != high . Очевидно, что мы сокращаем интервал (вдвое) каждой итерации.

Итак, поехали:

 int lgfloor(T value)
{
    assert(value > 0);

    int high = (sizeof(value) * 8);
    int low = 0;

    while (high > low 1)
    {
        int mid = (low   ((high - low) / 2));
        T guess = static_cast<T>(1) << mid;

        printf("high: %d, mid: %d, low: %dn", high, mid, low);

        if (value < guess)
            high = mid;
        else
            low = mid;
    }

    return low;
}
  

Я должен, конечно, отметить, что для этой точной цели в современном оборудовании есть специальные встроенные компоненты. Например, выполните поиск в руководстве по встроенным устройствам Intel для _BitScanReverse , который завершится за долю циклов, которые потребовались бы для приведенного выше кода.

Так или иначе, асимптотические времени выполнения, зависящие от разрядности, довольно бессмысленны при работе с типами фиксированной ширины, такими как C ‘ integral ‘ (хотя вопрос по-прежнему имеет образовательную ценность).

Бесконечный цикл возникает из-за этой строки:

  mid = (low   ((high - low) / 2));
  

если high и low отличаются на 1, результатом может быть mid == low а затем при условии, которое вызывает low = mid внутри цикла while, вы приводите к проверке одного и того же условия навсегда. Мое предложение было бы таким: если у вас есть low = mid в цикле, вы должны убедиться, что ваш mid != low в этом случае. Поэтому просто проверьте это перед назначением и сделайте low = mid 1 вместо этого, если это произойдет.

Решение должно быть найдено в lg(n) шагах, что означает, что инициализация, такая как low= 0 , high= 32 не будет работать, потому что это потребовало бы 5 шагов в каждом случае и не сработало бы для x большего, чем 2^32 . Правильное решение должно сочетать первый геометрический поиск, при котором вы удваиваете показатель степени, а затем стандартный дихотомический поиск.

 # Geometric search
low= 0
high= 1
while (1 << high) <= x:
    low= high
    high = high

# Dichotomic search
while high - low > 1:
    mid= (high   low) >> 1
    if x < mid:
        high= mid
    else:
        low= mid
  

Похоже, вам просто нужно сдвинуть if на правильные ‘log’ времена, пока у вас не будет ‘1’.

 using T = unsigned char;

int lgfloor(T value)
{
  assert(value > 0);

  int log = 0;
  while(value != 1) {
    value >> 1;
    log  ;
  }
  return log;
}