Qual é a sua técnica bit-wise preferida? [fechadas]

14

Há alguns dias, Anto, membro do StackExchange, perguntou sobre usos válidos para operadores bit-wise. Eu afirmei que o deslocamento era mais rápido do que multiplicar e dividir inteiros por potências de dois. O membro do StackExchange, Daemin, rebateu afirmando que o deslocamento da direita apresentava problemas com números negativos.

Nesse ponto, nunca havia pensado em usar os operadores de deslocamento com números inteiros assinados. Eu usei principalmente essa técnica no desenvolvimento de software de baixo nível; portanto, sempre usei números inteiros sem sinal. C executa mudanças lógicas em números inteiros sem sinal. Nenhuma atenção é dada ao bit de sinal ao executar um deslocamento lógico para a direita. Os bits desocupados são preenchidos com zeros. No entanto, C realiza uma operação de mudança aritmética ao deslocar um direito inteiro assinado. Os bits desocupados são preenchidos com o bit de sinal. Essa diferença faz com que um valor negativo seja arredondado em direção ao infinito em vez de ser truncado em direção a zero, o que é um comportamento diferente do que a divisão inteira assinada.

Alguns minutos de reflexão resultaram em uma solução de primeira ordem. A solução condicionalmente converte valores negativos em valores positivos antes de mudar. Um valor é condicionalmente convertido de volta para sua forma negativa após a operação de deslocamento ter sido realizada.

int a = -5;
int n = 1;

int negative = q < 0; 

a = negative ? -a : a; 
a >>= n; 
a = negative ? -a : a; 

O problema com esta solução é que as instruções de atribuição condicional são geralmente traduzidas para pelo menos uma instrução de salto, e instruções de salto podem ser caras em processadores que não decodificam os dois caminhos de instrução. Ter que recomeçar um pipeline de instruções duplica um bom desempenho em qualquer ganho de desempenho obtido pela mudança da divisão.

Com o acima exposto, acordei no sábado com a resposta para o problema de atribuição condicional. O problema de arredondamento que experimentamos ao executar uma operação de mudança aritmética só ocorre quando se trabalha com a representação de complemento de dois. Isso não ocorre com a representação de um complemento. A solução para o problema envolve converter o valor de um complemento de dois em um valor de complemento de um antes de executar a operação de deslocamento. Em seguida, temos que converter o valor do complemento de volta em um valor de complemento de dois. Surpreendentemente, podemos realizar este conjunto de operações sem converter condicionalmente valores negativos antes de realizar a operação de mudança.

int a = -5;
int n = 1;

register int sign = (a >> INT_SIZE_MINUS_1) & 1

a = (a - sign) >> n + sign;   

O valor negativo de um complemento de dois é convertido em um valor negativo do complemento subtraindo um. Por outro lado, o valor negativo do complemento de um é convertido em um valor negativo de complemento de dois adicionando um. O código listado acima funciona porque o bit de sinal é usado para converter de complemento de dois para um complemento e vice-versa . Apenas valores negativos terão seus bits de sinal definidos; portanto, a variável sign será igual a zero quando a for positivo.

Com o acima exposto, você pode pensar em outros hacks bit-wise como o acima que fizeram em sua bolsa de truques? Qual é o seu hack bit-wise favorito? Estou sempre à procura de novos hacks orientados para o desempenho.

    
por bit-twiddler 11.04.2011 / 05:52
fonte

0 respostas