Bit reordenar twiddling

Question

Eu preciso fazer um novo pedido arbitrário de um valor 7 bit (Sim, eu sei que eu deveria estar usando uma tabela) e estou querendo saber se existem hacks bit de fazer isso.

Exemplo:

// <b0, b1, b2, b3, b4, b5, b6> -> <b3, b2, b4, b1, b5, b0, b6>

// the naive way
out =
   (0x020 & In) << 5 |
   (0x008 & In) << 2 |
   (0x040 & In)      |
   (0x012 & In) >> 1 |
   (0x004 & In) >> 2 |
   (0x001 & In) >> 3;

// 6 ANDs, 5 ORs, 5 shifts = 16 ops

---

edit: Eu estava pensando em algo ao longo das linhas de este

Apenas por diversão e porque eu estava AFTK Estou tentando uma pesquisa de força bruta para soluções da forma:

((In * C1) >> C2) & 0x7f

Não há soluções encontradas.

Answer 1

Tenha um olhar para a saída do compilador de código "ingênuo", pode surpreendê-lo. Uma vez eu fiz algo assim e o compilador (VC ++ 2005) mudou completamente os valores de todos os ands e mudanças para mim para torná-los mais eficientes, por exemplo, eu estou certo de que iria remover seu "(0x001 & In) >> 3" .

Mas sim, se a remodelação é uma função fixa, em seguida, uma mesa é provavelmente o melhor.

Atualizar

Para um riso Olhei para a saída do compilador de VC ++ 2005 ....

Primeiro eu tentei um valor constante para "In" mas o compilador não se deixou enganar um pouco, produziu este código:

mov eax,469h

ie. -lo completamente otimizado-lo afastado.

Então ... Eu tentei uma entrada adequada e tem o seguinte:

00401D4F  mov         eax,ecx 
00401D51  and         eax,20h 
00401D54  shl         eax,3 
00401D57  mov         edx,ecx 
00401D59  and         edx,8 
00401D5C  or          eax,edx 
00401D5E  mov         edx,ecx 
00401D60  sar         edx,1 
00401D62  and         edx,2 
00401D65  or          edx,ecx 
00401D67  sar         edx,1 
00401D69  shl         eax,2 
00401D6C  and         edx,9 
00401D6F  or          eax,edx 
00401D71  and         ecx,40h 
00401D74  or          eax,ecx 

Isso é quatro operações de mudança, cinco ANDs, quatro RUP - nada mau para seis entradas. Provavelmente melhor do que a maioria das pessoas poderia fazer com a mão.

É, provavelmente, também otimizado para execução fora de ordem por isso vai ser ciclos de clock menos do que parece. : -)

Answer 2

O primeiro passo parece ser a de compreender uma solução matemática e otimizar isso.

veja aqui de bit hacks

Answer 3

Há uma abundância de cortes-twiddling bit para operações comuns, isto é, para inverter a ordem dos bits de uma palavra de 32 bits (10 cada de deslocamento, AND e OR, AFAICR).

Neste caso, com um mapeamento aparentemente completamente arbitrária da entrada à saída, não posso ver nenhuma maneira de limpar isso.

Use uma tabela de pesquisa:)

Answer 4

Antes de otimizar, você deve certificar-se de seu caminho 'ingênuo' está fazendo o que você pretende. Se eu fizer o seu código em uma função e executar este loop:

for (b=0;b<7;b++)
{
    i=1<<b;
    printf("%d: %02x -> %02x\n", b, i, shuffle(i));
}

Ela produz esta saída, o que contradiz os comentários. Na verdade, ele perde pedaços.

0: 01 -> 00
1: 02 -> 01
2: 04 -> 01
3: 08 -> 20
4: 10 -> 08
5: 20 -> 00
6: 40 -> 40

A fim de obter o shuffle você descreve, gostaria de codificá-lo como este:

   //    0 1 2 3 4 5 6 
   //-> 3 2 4 1 5 0 6
   (0x001 & In) << 3 |
   (0x004 & In) << 2 |
   (0x020 & In)      |
   (0x012 & In) << 1 |
   (0x008 & In) >> 2 |
   (0x020 & In) >> 5 ;