Проблема с поиском минимума (log2 (int)) с помощью бинарного поиска в O (log2 (amount_bits))

Решение должно быть найдено в 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

Похоже, вам просто нужно сдвинуться вправо, пока не получите «1».

using T = unsigned char;

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

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