Qual é a maneira mais rápida de operações de bits calcular uma paridade?

Question

Minha solução: (para cada pedaço do bloco de entrada, existe essa linha)

*parity ^= (((x[0] >> 30) & 0x00000001) * 0xc3e0d69f);

Todos os tipos são UINT32. Essa linha pega o segundo bit da entrada x, muda para o LSB e define todos os outros bits para zero. Em seguida, a paridade de 32 bits é xored com a paridade correspondente definida para este bit.

Descobri que essa solução de multiplicação é a maneira mais rápida de fazer esse XOR condicional. Existe uma maneira mais rápida?

Answer 1

Eu não entendo completamente que tipo de paridade você quer dizer, mas se essa linha de código está fazendo o que você deseja, pode ser melhorada.

Regra geral: para x em {0, 1} x * N == -x & N

Isso porque -x para 0 é reiniciado e para 1 é -1 no qual todos os bits estão definidos.

Portanto, a linha de código original pode ser reescrita como:

*parity ^= (-((x[0] >> 30) & 0x00000001) & 0xc3e0d69f);

Quais são as duas operações calculadas em menos tempo do que multiplicação em muitos microprocessadores, mas você deve verificar isso.

Além disso, o código pode aproveitar o turno assinado direito

*parity ^= (((int32_t)x[0] << 1 >> 31) & 0xc3e0d69f);

Primeiro turno Rshifts 30º bit na 31ª, que é o bit de sinal, e depois o segundo bit de sinal de estender em todos os outros como mudança na maioria das máquinas atuam como piso (x / 2^N), assim, o preenchimento mudou em bits com bit de sinal (abc...yz>>3 == aaaabc...yz).

Mas esses truques são declarados como comportamento indefinido no padrão C e assim não portátil. Use -os com cuidado.

Answer 2

Veja aqui Para alguns hacks legais para calcular a paridade de uma palavra, byte etc

Answer 3

Alguns processadores farão isso por você. Veja X86's bandeira de paridade.

Answer 4

Se eu entendi a pergunta corretamente, você está fazendo

for (i = 0; i < 32; i++)
    *parity ^= (((x[0] >> i) & 1) * SOME_CONST[i]); 

Nesse caso, é melhor usar tabelas de pesquisa:

for (i = 0; i < 4; i++)
    *parity ^= PARITY_LUT[i][ (x[0] >> (i*8)) & 0xFF];

Custaria 256kb, mas será muito mais rápido.

Answer 5

A tarefa de cálculo da paridade é equivalente à contagem de outras. Também chamado como "Bits Count Set", "População cont" ou simplesmente PopCount. Alguns dos processadores têm instruções eficientes para calculá -lo (PopCNT, VCNT).

Sugerirei usar o menor pedaço de pipas.

Pode ser acessado pelo montador embutido ou usando Builtins: __builtin_popcount ()/ __popcnt ()/ std :: bitset :: count () para gcc/ vs/ c ++

Pessoalmente, prefiro dar este trabalho ao compilador usando __builtin_parity ()