Jump to content
Sign in to follow this  
fredericopissarra

Hacker's Delight, recomendo a leitura...

Recommended Posts

Posted (edited)

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...

Edited by fredericopissarra
  • Curtir 2

Share this post


Link to post
Share on other sites
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!!! 🙂
  • Curtir 1

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...