Posição do bit menos significativo que está definido

Eu estou procurando uma maneira eficiente para determinar a posição do bit menos significativo que é definido em um inteiro, por exemplo, para 0x0FF0 seria 4.

Uma implementação trivial é esta:

unsigned GetLowestBitPos(unsigned value) { assert(value != 0); // handled separately unsigned pos = 0; while (!(value & 1)) { value >>= 1; ++pos; } return pos; } 

Alguma idéia de como extrair alguns ciclos disso?

(Nota: essa pergunta é para pessoas que gostam dessas coisas, não para as pessoas me dizerem que xyzotimização é mal.)

[edit] Obrigado a todos pelas ideias! Eu aprendi algumas outras coisas também. Legal!

O Bit Twiddling Hacks oferece uma excelente coleção de hacks bit, er, bit, com discussão de performance / otimização anexada. Minha solução favorita para o seu problema (daquele site) é “multiplicação e pesquisa”:

 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]; 

Referências úteis:

  • ” Usando as Sequências de Bruijn para Indexar um 1 em uma Palavra de Computador ” – Explicação sobre por que o código acima funciona.
  • ” Representação da Diretoria> Bitboards> BitScan ” – Análise detalhada deste problema, com foco particular na programação de xadrez

Por que não usar o ffs embutido? (Eu peguei uma página man do Linux, mas é mais amplamente disponível do que isso.)

ffs (3) – Linux man page

Nome

ffs – encontra o primeiro bit definido em uma palavra

Sinopse

 #include  int ffs(int i); #define _GNU_SOURCE #include  int ffsl(long int i); int ffsll(long long int i); 

Descrição

A function ffs () retorna a posição do primeiro bit (menos significativo) definido na palavra i. O bit menos significativo é a posição 1 e a posição mais significativa, por exemplo, 32 ou 64. As funções ffsll () e ffsl () fazem o mesmo, mas recebem argumentos de tamanho possivelmente diferente.

Valor de retorno

Essas funções retornam a posição do primeiro conjunto de bits ou 0 se nenhum bit for definido em i.

De acordo com

4.3BSD, POSIX.1-2001.

Notas

Os sistemas BSD possuem um protótipo em .

Há uma instrução de assembly x86 ( bsf ) que fará isso. 🙂

Mais otimizado ?!

Nota:

A otimização nesse nível é inerentemente dependente da arquitetura. Os processadores de hoje são muito complexos (em termos de predição de ramificação, falhas de cache, pipelining) que é tão difícil prever qual código é executado mais rapidamente em qual arquitetura. Diminuir as operações de 32 para 9 ou coisas assim pode até diminuir o desempenho em algumas arquiteturas. O código otimizado em uma única arquitetura pode resultar em um código pior no outro. Eu acho que você poderia otimizar isso para um processador específico ou deixá-lo como está e deixar o compilador escolher o que acha melhor.

A maioria das arquiteturas modernas terá algumas instruções para encontrar a posição do bit mais baixo definido, ou o bit mais alto definido, ou contar o número de zeros à esquerda, etc.

Se você tiver alguma instrução dessa class, você pode emular os outros com pouco custo.

Reserve um momento para trabalhar no papel e perceba que x & (x-1) apagará o bit mais baixo definido em x, e ( x & ~(x-1) ) retornará apenas o bit mais baixo definido, independentemente de uma arquitetura , tamanho da palavra, etc. Sabendo disso, é trivial usar o hardware levando a contagem zero ou o maior conjunto de bits para encontrar o bit mais baixo se não houver instruções explícitas para isso.

Se não houver nenhum suporte de hardware relevante, a implementação de multiplicação e pesquisa de zeros que levam a contagem dada aqui ou uma das da página Bit Twiddling Hacks pode ser convertida para dar o menor bit usando as identidades acima e tem a vantagem de ser sem filial.

A solução mais rápida (não intrínseca / não montadora) para isso é encontrar o byte mais baixo e, em seguida, usar esse byte em uma tabela de pesquisa de 256 inputs. Isso dá a você um pior desempenho de quatro instruções condicionais e um melhor caso de 1. Não apenas essa é a menor quantidade de instruções, mas a menor quantidade de ramificações que é super importante no hardware moderno.

Sua tabela (256 inputs de 8 bits) deve conter o índice do LSB para cada número no intervalo de 0 a 255. Você verifica cada byte do seu valor e localiza o byte diferente de zero, então use este valor para procurar o índice real.

Isso requer 256 bytes de memory, mas se a velocidade dessa function é tão importante, então esses 256 bytes valem a pena,

Por exemplo

 byte lowestBitTable[256] = { .... // left as an exercise for the reader to generate }; unsigned GetLowestBitPos(unsigned value) { // note that order to check indices will depend whether you are on a big // or little endian machine. This is for little-endian byte* bytes = (byte*)value; if (bytes[0]) return lowestBitTable[bytes[0]]; else if (bytes[1]) return lowestBitTable[bytes[1]] + 8; else if (bytes[2]) return lowestBitTable[bytes[2]] + 16; else return lowestBitTable[bytes[3]] + 24; } 

Weee, cargas de soluções e não um benchmark à vista. Vocês devem se envergonhar de si mesmos 😉

Minha máquina é um Intel i530 (2.9 GHz), executando o Windows 7 de 64 bits. Eu compilei com uma versão de 32 bits do MinGW.

 $ gcc --version gcc.exe (GCC) 4.7.2 $ gcc bench.c -o bench.exe -std=c99 -Wall -O2 $ bench Naive loop. Time = 2.91 (Original questioner) De Bruijn multiply. Time = 1.16 (Tykhyy) Lookup table. Time = 0.36 (Andrew Grant) FFS instruction. Time = 0.90 (ephemient) Branch free mask. Time = 3.48 (Dan / Jim Balter) Double hack. Time = 3.41 (DocMax) $ gcc bench.c -o bench.exe -std=c99 -Wall -O2 -march=native $ bench Naive loop. Time = 2.92 De Bruijn multiply. Time = 0.47 Lookup table. Time = 0.35 FFS instruction. Time = 0.68 Branch free mask. Time = 3.49 Double hack. Time = 0.92 

Meu código:

 #include  #include  #include  #define ARRAY_SIZE 65536 #define NUM_ITERS 5000 // Number of times to process array int find_first_bits_naive_loop(unsigned nums[ARRAY_SIZE]) { int total = 0; // Prevent compiler from optimizing out the code for (int j = 0; j < NUM_ITERS; j++) { for (int i = 0; i < ARRAY_SIZE; i++) { unsigned value = nums[i]; if (value == 0) continue; unsigned pos = 0; while (!(value & 1)) { value >>= 1; ++pos; } total += pos + 1; } } return total; } int find_first_bits_de_bruijn(unsigned nums[ARRAY_SIZE]) { static const int MultiplyDeBruijnBitPosition[32] = { 1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9, 32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10 }; int total = 0; // Prevent compiler from optimizing out the code for (int j = 0; j < NUM_ITERS; j++) { for (int i = 0; i < ARRAY_SIZE; i++) { unsigned int c = nums[i]; total += MultiplyDeBruijnBitPosition[((unsigned)((c & -c) * 0x077CB531U)) >> 27]; } } return total; } unsigned char lowestBitTable[256]; int get_lowest_set_bit(unsigned num) { unsigned mask = 1; for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) { if (num & mask) { return cnt; } } return 0; } int find_first_bits_lookup_table(unsigned nums[ARRAY_SIZE]) { int total = 0; // Prevent compiler from optimizing out the code for (int j = 0; j < NUM_ITERS; j++) { for (int i = 0; i < ARRAY_SIZE; i++) { unsigned int value = nums[i]; // note that order to check indices will depend whether you are on a big // or little endian machine. This is for little-endian unsigned char *bytes = (unsigned char *)&value; if (bytes[0]) total += lowestBitTable[bytes[0]]; else if (bytes[1]) total += lowestBitTable[bytes[1]] + 8; else if (bytes[2]) total += lowestBitTable[bytes[2]] + 16; else total += lowestBitTable[bytes[3]] + 24; } } return total; } int find_first_bits_ffs_instruction(unsigned nums[ARRAY_SIZE]) { int total = 0; // Prevent compiler from optimizing out the code for (int j = 0; j < NUM_ITERS; j++) { for (int i = 0; i < ARRAY_SIZE; i++) { total += __builtin_ffs(nums[i]); } } return total; } int find_first_bits_branch_free_mask(unsigned nums[ARRAY_SIZE]) { int total = 0; // Prevent compiler from optimizing out the code for (int j = 0; j < NUM_ITERS; j++) { for (int i = 0; i < ARRAY_SIZE; i++) { unsigned value = nums[i]; int i16 = !(value & 0xffff) << 4; value >>= i16; int i8 = !(value & 0xff) << 3; value >>= i8; int i4 = !(value & 0xf) << 2; value >>= i4; int i2 = !(value & 0x3) << 1; value >>= i2; int i1 = !(value & 0x1); int i0 = (value >> i1) & 1? 0 : -32; total += i16 + i8 + i4 + i2 + i1 + i0 + 1; } } return total; } int find_first_bits_double_hack(unsigned nums[ARRAY_SIZE]) { int total = 0; // Prevent compiler from optimizing out the code for (int j = 0; j < NUM_ITERS; j++) { for (int i = 0; i < ARRAY_SIZE; i++) { unsigned value = nums[i]; double d = value ^ (value - !!value); total += (((int*)&d)[1]>>20)-1022; } } return total; } int main() { unsigned nums[ARRAY_SIZE]; for (int i = 0; i < ARRAY_SIZE; i++) { nums[i] = rand() + (rand() << 15); } for (int i = 0; i < 256; i++) { lowestBitTable[i] = get_lowest_set_bit(i); } clock_t start_time, end_time; int result; start_time = clock(); result = find_first_bits_naive_loop(nums); end_time = clock(); printf("Naive loop. Time = %.2f, result = %d\n", (end_time - start_time) / (double)(CLOCKS_PER_SEC), result); start_time = clock(); result = find_first_bits_de_bruijn(nums); end_time = clock(); printf("De Bruijn multiply. Time = %.2f, result = %d\n", (end_time - start_time) / (double)(CLOCKS_PER_SEC), result); start_time = clock(); result = find_first_bits_lookup_table(nums); end_time = clock(); printf("Lookup table. Time = %.2f, result = %d\n", (end_time - start_time) / (double)(CLOCKS_PER_SEC), result); start_time = clock(); result = find_first_bits_ffs_instruction(nums); end_time = clock(); printf("FFS instruction. Time = %.2f, result = %d\n", (end_time - start_time) / (double)(CLOCKS_PER_SEC), result); start_time = clock(); result = find_first_bits_branch_free_mask(nums); end_time = clock(); printf("Branch free mask. Time = %.2f, result = %d\n", (end_time - start_time) / (double)(CLOCKS_PER_SEC), result); start_time = clock(); result = find_first_bits_double_hack(nums); end_time = clock(); printf("Double hack. Time = %.2f, result = %d\n", (end_time - start_time) / (double)(CLOCKS_PER_SEC), result); } 

OMG tem isso apenas em espiral.

O que a maioria desses exemplos está faltando é um pouco de entendimento sobre como todo o hardware funciona.

Sempre que você tem um ramo, o processador tem que adivinhar qual ramificação será tomada. O pipe de instruções é carregado com as instruções que levam ao caminho adivinhado. Se a CPU tiver adivinhado errado, o pipe de instrução será liberado e a outra ramificação deverá ser carregada.

Considere o loop while simples no topo. O palpite será ficar dentro do loop. Será errado pelo menos uma vez quando sair do loop. Isso irá liberar o tubo de instruções. Esse comportamento é um pouco melhor do que adivinhar que ele irá deixar o loop, caso em que ele iria liberar o pipe de instrução em cada iteração.

A quantidade de ciclos de CPU perdidos varia muito de um tipo de processador para outro. Mas você pode esperar entre 20 e 150 ciclos de CPU perdidos.

O próximo grupo pior é onde você pensa em salvar algumas iterações dividindo o valor em partes menores e adicionando várias outras ramificações. Cada uma dessas ramificações adiciona uma oportunidade adicional de liberar o canal de instruções e custar outros 20 a 150 ciclos de clock.

Vamos considerar o que acontece quando você procura um valor em uma tabela. Provavelmente, o valor não está atualmente no cache, pelo menos não na primeira vez que sua function é chamada. Isso significa que a CPU fica paralisada enquanto o valor é carregado do cache. Novamente, isso varia de uma máquina para outra. Os novos chips da Intel realmente usam isso como uma oportunidade para trocar threads enquanto o segmento atual está aguardando a conclusão da carga do cache. Isso pode facilmente ser mais caro do que um flush de tubulação de instruções, no entanto, se você estiver executando esta operação várias vezes, é provável que ela ocorra somente uma vez.

Claramente, a solução de tempo constante mais rápida é aquela que envolve matemática determinística. Uma solução pura e elegante.

Minhas desculpas se isso já foi coberto.

Todo compilador que eu uso, exceto o XCODE AFAIK, possui intrínsecos de compilador tanto para os bits de avanço quanto para o de bits reverso. Estes irão compilar para uma única instrução de assembly na maioria dos hardwares sem cache Miss, nenhum Branch Miss-Prediction e nenhum outro programador gerou obstáculos.

Para compiladores Microsoft use _BitScanForward & _BitScanReverse.
Para o GCC, use __builtin_ffs, __builtin_clz, __builtin_ctz.

Além disso, por favor, abstenha-se de postar uma resposta e potencialmente novos participantes enganosos se você não estiver adequadamente informado sobre o assunto que está sendo discutido.

Desculpe eu esqueci completamente de fornecer uma solução .. Este é o código que eu uso no IPAD que não tem instrução de nível de assembly para a tarefa:

 unsigned BitScanLow_BranchFree(unsigned value) { bool bwl = (value & 0x0000ffff) == 0; unsigned I1 = (bwl * 15); value = (value >> I1) & 0x0000ffff; bool bbl = (value & 0x00ff00ff) == 0; unsigned I2 = (bbl * 7); value = (value >> I2) & 0x00ff00ff; bool bnl = (value & 0x0f0f0f0f) == 0; unsigned I3 = (bnl * 3); value = (value >> I3) & 0x0f0f0f0f; bool bsl = (value & 0x33333333) == 0; unsigned I4 = (bsl * 1); value = (value >> I4) & 0x33333333; unsigned result = value + I1 + I2 + I3 + I4 - 1; return result; } 

A coisa a entender aqui é que não é a comparação que é cara, mas o ramo que ocorre após a comparação. A comparação neste caso é forçada para um valor de 0 ou 1 com o valor de == 0, e o resultado é usado para combinar a matemática que teria ocorrido em ambos os lados do ramo.

Editar:

O código acima está totalmente quebrado. Este código funciona e ainda é livre de ramificação (se otimizado):

 int BitScanLow_BranchFree(ui value) { int i16 = !(value & 0xffff) << 4; value >>= i16; int i8 = !(value & 0xff) << 3; value >>= i8; int i4 = !(value & 0xf) << 2; value >>= i4; int i2 = !(value & 0x3) << 1; value >>= i2; int i1 = !(value & 0x1); int i0 = (value >> i1) & 1? 0 : -32; return i16 + i8 + i4 + i2 + i1 + i0; } 

Isso retorna -1 se for dado 0. Se você não se preocupa com 0 ou fica feliz em receber 31 para 0, remova o cálculo de i0, economizando um bom tempo.

Inspirado por este post semelhante que envolve a busca por um bit definido, eu ofereço o seguinte:

 unsigned GetLowestBitPos(unsigned value) { double d = value ^ (value - !!value); return (((int*)&d)[1]>>20)-1023; } 

Prós:

  • sem loops
  • sem ramificação
  • funciona em tempo constante
  • processa value = 0 retornando um resultado que não está fora dos limites
  • apenas duas linhas de código

Contras:

  • assume pouco endianness como codificado (pode ser corrigido alterando as constantes)
  • assume que o dobro é um flutuante IEEE real * 8 (IEEE 754)

Atualização: Como apontado nos comentários, um sindicato é uma implementação mais limpa (para C, pelo menos) e seria semelhante a:

 unsigned GetLowestBitPos(unsigned value) { union { int i[2]; double d; } temp = { .d = value ^ (value - !!value) }; return (temp.i[1] >> 20) - 1023; } 

Isso pressupõe ints de 32 bits com armazenamento little-endian para tudo (pense em processadores x86).

Isso pode ser feito com um pior caso de menos de 32 operações:

Princípio: A verificação de 2 ou mais bits é tão eficiente quanto a verificação de 1 bit.

Assim, por exemplo, não há nada que o impeça de verificar qual deles está agrupando primeiro e depois verificar cada bit do menor para o maior desse grupo.

Assim…
se você verificar 2 bits de cada vez, você tem no pior dos casos (Nbits / 2) + 1 total de cheques.
se você verificar 3 bits de cada vez, você tem no pior dos casos (Nbits / 3) + 2 cheques no total.

O ideal seria verificar em grupos de 4. O que exigiria no pior dos casos 11 operações em vez de 32.

O melhor caso vai desde a verificação de 1 de seus algoritmos até 2 verificações, se você usar essa ideia de agrupamento. Mas esse cheque extra 1 no melhor caso vale a pena para a pior das hipóteses.

Nota: eu escrevo na íntegra em vez de usar um loop porque é mais eficiente assim.

 int getLowestBitPos(unsigned int value) { //Group 1: Bits 0-3 if(value&0xf) { if(value&0x1) return 0; else if(value&0x2) return 1; else if(value&0x4) return 2; else return 3; } //Group 2: Bits 4-7 if(value&0xf0) { if(value&0x10) return 4; else if(value&0x20) return 5; else if(value&0x40) return 6; else return 7; } //Group 3: Bits 8-11 if(value&0xf00) { if(value&0x100) return 8; else if(value&0x200) return 9; else if(value&0x400) return 10; else return 11; } //Group 4: Bits 12-15 if(value&0xf000) { if(value&0x1000) return 12; else if(value&0x2000) return 13; else if(value&0x4000) return 14; else return 15; } //Group 5: Bits 16-19 if(value&0xf0000) { if(value&0x10000) return 16; else if(value&0x20000) return 17; else if(value&0x40000) return 18; else return 19; } //Group 6: Bits 20-23 if(value&0xf00000) { if(value&0x100000) return 20; else if(value&0x200000) return 21; else if(value&0x400000) return 22; else return 23; } //Group 7: Bits 24-27 if(value&0xf000000) { if(value&0x1000000) return 24; else if(value&0x2000000) return 25; else if(value&0x4000000) return 26; else return 27; } //Group 8: Bits 28-31 if(value&0xf0000000) { if(value&0x10000000) return 28; else if(value&0x20000000) return 29; else if(value&0x40000000) return 30; else return 31; } return -1; } 

Por que não usar pesquisa binária ? Isso sempre será concluído após 5 operações (assumindo int tamanho de 4 bytes):

 if (0x0000FFFF & value) { if (0x000000FF & value) { if (0x0000000F & value) { if (0x00000003 & value) { if (0x00000001 & value) { return 1; } else { return 2; } } else { if (0x0000004 & value) { return 3; } else { return 4; } } } else { ... } else { ... } else { ... 

Outro método (divisão de módulo e pesquisa) merece uma menção especial aqui do mesmo link fornecido por @ anton-tykhyy. Esse método é muito semelhante em desempenho ao método de multiplicação e pesquisa de DeBruijn, com uma pequena, mas importante diferença.

divisão de módulo e pesquisa

  unsigned int v; // find the number of trailing zeros in v int r; // put the result in r static const int Mod37BitPosition[] = // map a bit value mod 37 to its position { 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18 }; r = Mod37BitPosition[(-v & v) % 37]; 

método de divisão e consulta de módulo retorna valores diferentes para v = 0x00000000 e v = FFFFFFFF, enquanto que DeBruijn multiplica e o método de pesquisa retorna zero em ambas as inputs.

teste:-

 unsigned int n1=0x00000000, n2=0xFFFFFFFF; MultiplyDeBruijnBitPosition[((unsigned int )((n1 & -n1) * 0x077CB531U)) >> 27]); /* returns 0 */ MultiplyDeBruijnBitPosition[((unsigned int )((n2 & -n2) * 0x077CB531U)) >> 27]); /* returns 0 */ Mod37BitPosition[(((-(n1) & (n1))) % 37)]); /* returns 32 */ Mod37BitPosition[(((-(n2) & (n2))) % 37)]); /* returns 0 */ 

De acordo com a página Chess Programming BitScan e minhas próprias medidas, subtrair e xor é mais rápido que negar e mascarar.

(Observe que, se você for contar os zeros à direita em 0 , o método como eu retornará 63 enquanto o negate e a máscara retornarão 0 )

Aqui está uma subtração de 64 bits e xor:

 unsigned long v; // find the number of trailing zeros in 64-bit v int r; // result goes here static const int MultiplyDeBruijnBitPosition[64] = { 0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61, 54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62, 46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45, 25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63 }; r = MultiplyDeBruijnBitPosition[((uint32_t)((v ^ (v-1)) * 0x03F79D71B4CB0A89U)) >> 58]; 

Para referência, aqui está uma versão de 64 bits do método negate e mask:

 unsigned long v; // find the number of trailing zeros in 64-bit v int r; // result goes here static const int MultiplyDeBruijnBitPosition[64] = { 0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4, 62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5, 63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11, 46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6 }; r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x03F79D71B4CB0A89U)) >> 58]; 

Você pode verificar se algum dos bits de ordem inferior está definido. Se sim, veja a ordem inferior dos bits restantes. por exemplo,:

32bit int – verifique se algum dos primeiros 16 estão definidos. Em caso afirmativo, verifique se algum dos primeiros 8 está definido. se então, ….

se não, verifique se algum dos 16 superiores está definido.

Essencialmente, é a pesquisa binária.

Veja minha resposta aqui para saber como fazer isso com uma única instrução x86, exceto que para encontrar o bit de conjunto menos significativo, você desejará a instrução BSF (“bit scan forward”) em vez de BSR descrita lá.

Mais uma solução, não a mais rápida possível, mas parece muito boa.
Pelo menos não tem filiais. 😉

 uint32 x = ...; // 0x00000001 0x0405a0c0 0x00602000 x |= x << 1; // 0x00000003 0x0c0fe1c0 0x00e06000 x |= x << 2; // 0x0000000f 0x3c3fe7c0 0x03e1e000 x |= x << 4; // 0x000000ff 0xffffffc0 0x3fffe000 x |= x << 8; // 0x0000ffff 0xffffffc0 0xffffe000 x |= x << 16; // 0xffffffff 0xffffffc0 0xffffe000 // now x is filled with '1' from the least significant '1' to bit 31 x = ~x; // 0x00000000 0x0000003f 0x00001fff // now we have 1's below the original least significant 1 // let's count them x = x & 0x55555555 + (x >> 1) & 0x55555555; // 0x00000000 0x0000002a 0x00001aaa x = x & 0x33333333 + (x >> 2) & 0x33333333; // 0x00000000 0x00000024 0x00001444 x = x & 0x0f0f0f0f + (x >> 4) & 0x0f0f0f0f; // 0x00000000 0x00000006 0x00000508 x = x & 0x00ff00ff + (x >> 8) & 0x00ff00ff; // 0x00000000 0x00000006 0x0000000d x = x & 0x0000ffff + (x >> 16) & 0x0000ffff; // 0x00000000 0x00000006 0x0000000d // least sign.bit pos. was: 0 6 13 
 unsigned GetLowestBitPos(unsigned value) { if (value & 1) return 1; if (value & 2) return 2; if (value & 4) return 3; if (value & 8) return 4; if (value & 16) return 5; if (value & 32) return 6; if (value & 64) return 7; if (value & 128) return 8; if (value & 256) return 9; if (value & 512) return 10; if (value & 1024) return 11; if (value & 2048) return 12; if (value & 4096) return 13; if (value & 8192) return 14; if (value & 16384) return 15; if (value & 32768) return 16; if (value & 65536) return 17; if (value & 131072) return 18; if (value & 262144) return 19; if (value & 524288) return 20; if (value & 1048576) return 21; if (value & 2097152) return 22; if (value & 4194304) return 23; if (value & 8388608) return 24; if (value & 16777216) return 25; if (value & 33554432) return 26; if (value & 67108864) return 27; if (value & 134217728) return 28; if (value & 268435456) return 29; if (value & 536870912) return 30; return 31; } 

50% of all numbers will return on the first line of code.

75% of all numbers will return on the first 2 lines of code.

87% of all numbers will return in the first 3 lines of code.

94% of all numbers will return in the first 4 lines of code.

97% of all numbers will return in the first 5 lines of code.

etc.

I think people that are complaining on how inefficient the worst case scenario for this code don’t understand how rare that condition will happen.

Found this clever trick using ‘magic masks’ in “The art of programming, part 4”, which does it in O(log(n)) time for n-bit number. [with log(n) extra space]. Typical solutions checking for the set bit is either O(n) or need O(n) extra space for a look up table, so this is a good compromise.

Magic masks:

 m0 = (...............01010101) m1 = (...............00110011) m2 = (...............00001111) m3 = (.......0000000011111111) .... 

Key idea: No of trailing zeros in x = 1 * [(x & m0) = 0] + 2 * [(x & m1) = 0] + 4 * [(x & m2) = 0] + …

 int lastSetBitPos(const uint64_t x) { if (x == 0) return -1; //For 64 bit number, log2(64)-1, ie; 5 masks needed int steps = log2(sizeof(x) * 8); assert(steps == 6); //magic masks uint64_t m[] = { 0x5555555555555555, // .... 010101 0x3333333333333333, // .....110011 0x0f0f0f0f0f0f0f0f, // ...00001111 0x00ff00ff00ff00ff, //0000000011111111 0x0000ffff0000ffff, 0x00000000ffffffff }; //Firstly extract only the last set bit uint64_t y = x & -x; int trailZeros = 0, i = 0 , factor = 0; while (i < steps) { factor = ((y & m[i]) == 0 ) ? 1 : 0; trailZeros += factor * pow(2,i); ++i; } return (trailZeros+1); } 

If C++11 is available for you, a compiler sometimes can do the task for you 🙂

 constexpr std::uint64_t lssb(const std::uint64_t value) { return !value ? 0 : (value % 2 ? 1 : lssb(value >> 1) + 1); } 

Result is 1-based index.

This is in regards of @Anton Tykhyy answer

Here is my C++11 constexpr implementation doing away with casts and removing a warning on VC++17 by truncating a 64bit result to 32 bits:

 constexpr uint32_t DeBruijnSequence[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 }; constexpr uint32_t ffs ( uint32_t value ) { return DeBruijnSequence[ (( ( value & ( -static_cast(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF) >> 27]; } 

To get around the issue of 0x1 and 0x0 both returning 0 you can do:

 constexpr uint32_t ffs ( uint32_t value ) { return (!value) ? 32 : DeBruijnSequence[ (( ( value & ( -static_cast(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF) >> 27]; } 

but if the compiler can’t or won’t preprocess the call it will add a couple of cycles to the calculation.

Finally, if interested, here’s a list of static asserts to check that the code does what is intended to:

 static_assert (ffs(0x1) == 0, "Find First Bit Set Failure."); static_assert (ffs(0x2) == 1, "Find First Bit Set Failure."); static_assert (ffs(0x4) == 2, "Find First Bit Set Failure."); static_assert (ffs(0x8) == 3, "Find First Bit Set Failure."); static_assert (ffs(0x10) == 4, "Find First Bit Set Failure."); static_assert (ffs(0x20) == 5, "Find First Bit Set Failure."); static_assert (ffs(0x40) == 6, "Find First Bit Set Failure."); static_assert (ffs(0x80) == 7, "Find First Bit Set Failure."); static_assert (ffs(0x100) == 8, "Find First Bit Set Failure."); static_assert (ffs(0x200) == 9, "Find First Bit Set Failure."); static_assert (ffs(0x400) == 10, "Find First Bit Set Failure."); static_assert (ffs(0x800) == 11, "Find First Bit Set Failure."); static_assert (ffs(0x1000) == 12, "Find First Bit Set Failure."); static_assert (ffs(0x2000) == 13, "Find First Bit Set Failure."); static_assert (ffs(0x4000) == 14, "Find First Bit Set Failure."); static_assert (ffs(0x8000) == 15, "Find First Bit Set Failure."); static_assert (ffs(0x10000) == 16, "Find First Bit Set Failure."); static_assert (ffs(0x20000) == 17, "Find First Bit Set Failure."); static_assert (ffs(0x40000) == 18, "Find First Bit Set Failure."); static_assert (ffs(0x80000) == 19, "Find First Bit Set Failure."); static_assert (ffs(0x100000) == 20, "Find First Bit Set Failure."); static_assert (ffs(0x200000) == 21, "Find First Bit Set Failure."); static_assert (ffs(0x400000) == 22, "Find First Bit Set Failure."); static_assert (ffs(0x800000) == 23, "Find First Bit Set Failure."); static_assert (ffs(0x1000000) == 24, "Find First Bit Set Failure."); static_assert (ffs(0x2000000) == 25, "Find First Bit Set Failure."); static_assert (ffs(0x4000000) == 26, "Find First Bit Set Failure."); static_assert (ffs(0x8000000) == 27, "Find First Bit Set Failure."); static_assert (ffs(0x10000000) == 28, "Find First Bit Set Failure."); static_assert (ffs(0x20000000) == 29, "Find First Bit Set Failure."); static_assert (ffs(0x40000000) == 30, "Find First Bit Set Failure."); static_assert (ffs(0x80000000) == 31, "Find First Bit Set Failure."); 

Here is one simple alternative, even though finding logs is a bit costly.

 if(n == 0) return 0; return log2(n & -n)+1; //Assuming the bit index starts from 1 

recently I see that singapore’s premier posted a program he wrote on facebook, there is one line to mention it..

The logic is simply “value & -value”, suppose you have 0x0FF0, then, 0FF0 & (F00F+1) , which equals 0x0010, that means the lowest 1 is in the 4th bit.. 🙂

If you have the resources, you can sacrifice memory in order to improve the speed:

 static const unsigned bitPositions[MAX_INT] = { 0, 0, 1, 0, 2, /* ... */ }; unsigned GetLowestBitPos(unsigned value) { assert(value != 0); // handled separately return bitPositions[value]; } 

Note: This table would consume at least 4 GB (16 GB if we leave the return type as unsigned ). This is an example of trading one limited resource (RAM) for another (execution speed).

If your function needs to remain portable and run as fast as possible at any cost, this would be the way to go. In most real-world applications, a 4GB table is unrealistic.