Как найти n где k = 2^n

Question

Если я знаю целое число k = 2^n, как я могу эффективно найти n? Другими словами, если я знаю, что один бит в целочисленном наборе задан, как я могу получить местоположение бита?

Идея состоит в том, чтобы найти вес Хэмминга k-1, но есть ли другие более простые способы, о которых я не думаю?

Answer 1

Bit Twiddling Hacks есть много удивительных (и неясных, ориентированных на производительность) бит-хаков. Лучше всего для вашего использования, кажется, используется умножение и поиск.

unsigned int v; // find the number of trailing zeros in 32-bit v 
int r;   // result goes here 
static const int MultiplyDeBruijnBitPosition[32] = 
{ 
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
}; 
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27]; 

This page обеспечивает детальный анализ проблемы с акцентом на шахматном программировании.

Ответить с цитированием here. PS: Не знал, как отдать должное автору по этому вопросу, и поэтому написал его вот так.