Hacker's Delight, recomendo a leitura...

[fredericopissarra]

O livro citado tem um montão de "macetes" interessantes, especialmente para o desenvolvedor que está interessado em baixo nível e alta-performance. Eis um exemplo: Imagine que você queira fazer uma rotina que zere o primeiro bit setado em uma variável inteira qualquer. Por exemplo,  se o valor binário for 0b10101000, ele deverá ser convertido para 0b10100000 (note os bits em vermelho)... A aproximação clássica seria contar quantos bits zerados estão do lado direito para montar uma máscara e aplicá-la ao valor original. Algo assim:

unsigned ct1b_traditional( unsigned int x )
{
  int bit;
  unsigned int tmp;
 
  // Se x for 0, não temos 1s.
  if ( ! x )
    return 0;
 
  // Procura pelo bit 1 mais à direita.
  tmp = x;
  bit = 0;
  while ( ! ( tmp & 1 ) )
  {
    tmp >>= 1;  // ISSO pode dar craca com 'int'.
    bit++;
  }
 
  // Cria a máscara para zerar o bit.
  tmp = ~(1 << bit);
 
  // Aplica a máscara.
  return x & tmp;
}

Uma maneira melhor seria usar uma função especializada para substituir o loop. Na plataforma x86, desde os 386, temos a instrução BSF (Bit Scan Forward) que procura por um bit 1 da direita para esquerda. No GCC essa instrução é manifestada pela função __builtin_ctz() -- onde "ctz" significa "count trailling zeros". A função acima fica:

unsigned int ct1b_builtin( unsigned int x )
{
  int bit;
 
  if ( ! x )
    return 0;
 
  // ctz = count trailling zeros.
  bit = __builtin_ctz( x );
 
  return x & ~( 1U << bit );
}

Para efeitos de comparação, eis as duas funções, compiladas com a opção de otimização -O2 para o modo x86-64, no GCC (lado a lado):

ct1b_traditional:      ct1b_builtin:  
  xor  eax,eax           xor  eax,eax
  test edi,edi           test edi,edi
  je   .L1               je   .L1
  test dil,1             xor  ecx,ecx
  mov  eax,-2            mov  eax,-2
  jne  .L3               bsf  ecx,edi
  mov  eax,edi           rol  eax,cl
  xor  ecx,ecx           and  eax,edi
.L4:                   .L1:
  shr  eax,1             ret
  add  ecx,1     
  test al,1      
  je   .L4       
  mov  eax,-2
  rol  eax,cl
.L3:
  and  eax,edi
.L1:
  ret

Acontece que tem um jeito mais rápido, mas não tão evidente:

unsigned int ct1b_fast( unsigned int x ) { return x & (x - 1); }

O código gerado, nas mesmas condições, é:

ct1b_fast:
  lea  eax,[rdi - 1]
  and  eax,edi
  ret

E funciona exatamente do mesmo jeito!!! E tem outra vantagem: A função acima funciona tanto com tipos integrais sinalizados quanto com não sinalizados...

Esse e outros macetes (alguns bem escabrosos) estão no livro...

[fredericopissarra]

Ahhh... ctb1, nas minhas funções, significa "clear trailling bit 1".

[fredericopissarra]

Pra quem interessar: Eis (aqui) o documento que deu origem ao livro Hacker's Delight (HAKMEM, do MIT, em 1972):

 

Atenção: Os fragmentos de código contidos no documento estão em ASSEMBLY do PDP-6 ou PDP-10. O troço é velho pacas! Dá pra sacar porque ele é datilografado!!! ?