Operação bitwise

Os turnos de bits são por vezes considerados operações bitwise, porque tratam um valor como uma série de bits e não como uma quantidade numérica. Nestas operações os dígitos são movidos, ou deslocados, para a esquerda ou para a direita. Os registos num processador de computador têm uma largura fixa, pelo que alguns bits serão “deslocados para fora” do registo numa extremidade, enquanto o mesmo número de bits são “deslocados para dentro” a partir da outra extremidade; as diferenças entre os operadores de deslocamento de bits residem na forma como determinam os valores dos bits deslocados para dentro.

endereçamento de bitsEdit

Se a largura do registo (frequentemente 32 ou mesmo 64) for maior do que o número de bits (normalmente 8) da unidade endereçável mais pequena (elemento atómico), frequentemente chamado byte, as operações de deslocamento induzem um esquema de endereçamento nos bits.Desconsiderando os efeitos de limite em ambas as extremidades do registo, as operações de deslocamento aritmético e lógico comportam-se da mesma forma, e um deslocamento por 8 posições de bits transporta o padrão de bits por 1 posição de byte da seguinte forma:

Shift AritEdit

Deslocamento aritmético esquerdo

Deslocamento aritmético direito

Num deslocamento aritmético, os bocados que são deslocados para fora de qualquer uma das extremidades são descartados. Num deslocamento aritmético esquerdo, os zeros são deslocados para a direita; num deslocamento aritmético direito, o bit de sinal (o MSB no complemento de dois) é deslocado para a esquerda, preservando assim o sinal do operando.

Este exemplo utiliza um registo de 8 bits, interpretado como complemento de dois:

 00010111 (decimal +23) LEFT-SHIFT= 00101110 (decimal +46)

 10010111 (decimal −105) RIGHT-SHIFT= 11001011 (decimal −53)

No primeiro caso, o dígito mais à esquerda foi deslocado para além do fim do registo, e um novo 0 foi deslocado para a posição mais à direita. No segundo caso, o 1 mais à direita foi deslocado para fora (talvez para a bandeira de transporte), e um novo 1 foi copiado para a posição mais à esquerda, preservando o sinal do número. Os turnos múltiplos são por vezes encurtados para um único turno por um certo número de dígitos. Por exemplo:

 00010111 (decimal +23) LEFT-SHIFT-BY-TWO= 01011100 (decimal +92)

Um turno aritmético esquerdo por n é equivalente a multiplicar por 2n (desde que o valor não transborde), enquanto um turno aritmético direito por n de um valor complementar de dois é equivalente a dividir por 2n e arredondar para o infinito negativo. Se o número binário for tratado como um complemento, então a mesma operação de desvio à direita resulta na divisão por 2n e arredondamento para zero.

Deslocamento lógicoEditar

Mudança lógica direita

Mudança lógica esquerda

Num turno lógico, Os zeros são deslocados para substituir os pedaços descartados. Portanto, os turnos lógico e aritmético esquerdo são exactamente os mesmos.

No entanto, como o turno lógico direito insere o valor 0 bits no bit mais significativo, em vez de copiar o bit de sinal, é ideal para números binários não assinados, enquanto que o turno aritmético direito é ideal para números binários complementares de dois dígitos assinados.

Circular shiftEdit

Outra forma de deslocamento é o deslocamento circular, rotação bit a bit ou rotação bit a bit.

RotateEdit

Deslocamento circular esquerdo ou rotação /div>

Deslocamento circular direito ou rotate

Nesta operação, por vezes chamados rotate no carry, os bits são “rotacionados” como se as extremidades esquerda e direita do registo estivessem unidas. O valor que é deslocado para a direita durante um deslocamento para a esquerda é o valor que foi deslocado para a esquerda, e vice versa para uma operação de deslocamento para a direita. Isto é útil se for necessário reter todos os bits existentes, e é frequentemente utilizado em criptografia digital.

Rodar através de carryEdit

rotação à esquerda através de carry

rotação direita através de carry

Rotate through carry é uma variante da operação de rotação, onde o bit que é deslocado para dentro (em cada extremidade) é o antigo valor da bandeira de transporte, e o bit que é deslocado para fora (na outra extremidade) torna-se o novo valor da bandeira de transporte.

Uma única rotação através de carry pode simular uma deslocação lógica ou aritmética de uma posição, configurando previamente a bandeira de carry. Por exemplo, se a bandeira de transporte contém 0, então x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE é um deslocamento lógico à direita, e se a bandeira de transporte contém uma cópia do bit do sinal, então x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE é um deslocamento aritmético à direita. Por esta razão, alguns microcontroladores, como os PICs de baixa extremidade, apenas têm rotação e rotação através de carry, e não se preocupam com instruções aritméticas ou lógicas de deslocamento.

Rotate through carry é especialmente útil quando se realizam deslocamentos em números maiores do que o tamanho de palavra nativo do processador, porque se um grande número é armazenado em dois registos, o bit que é deslocado de uma extremidade do primeiro registo deve entrar na outra extremidade do segundo. Com a rotatividade de transporte, esse bit é “guardado” na bandeira de transporte durante o primeiro turno, pronto a ser transportado durante o segundo turno sem qualquer preparação extra.

Em línguas de alto nívelEditar

C-familyEdit

Em línguas C-family, os operadores do turno lógico são “<<” para o turno esquerdo e “>>” para o turno direito. O número de lugares para o turno é dado como o segundo argumento ao operador. Por exemplo,

x = y << 2;

assigns x o resultado do deslocamento y para a esquerda por dois bits, o que equivale a uma multiplicação por quatro.

Deslocações podem resultar em comportamento definido pela implementação ou comportamento indefinido, pelo que se deve ter cuidado ao utilizá-los. O resultado da mudança por uma contagem de bits maior ou igual ao tamanho da palavra é um comportamento indefinido em C e C++. O deslocamento da direita um valor negativo é definido pela implementação e não recomendado pela boa prática de codificação; o resultado do deslocamento da esquerda um valor assinado é indefinido se o resultado não puder ser representado no tipo de resultado.

Em C#, o deslocamento da direita é um deslocamento aritmético quando o primeiro operando é um int ou longo. Se o primeiro operando for do tipo uint ou ulong, o turno da direita é um turno lógico.

Turnos circularesEdit

A família C de idiomas não tem um operador rotativo, mas pode ser sintetizado a partir dos operadores de turno. Deve ter-se o cuidado de assegurar que a declaração é bem formada para evitar comportamentos e ataques de tempo indefinidos em software com requisitos de segurança. Por exemplo, uma implementação ingénua que deixa girar um valor de 32-bit sem assinatura x por n posições é simples:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (32 - n));

No entanto, um deslocamento por 0 bits resulta em comportamento indefinido na expressão da mão direita (x >> (32 - n)) porque 32 - 032, e 32 está fora do intervalo inclusive. Uma segunda tentativa pode resultar em:

uint32_t x = ..., n = ...;uint32_t y = n ? (x << n) | (x >> (32 - n)) : x;

onde a quantidade de turno é testada para garantir que não introduz um comportamento indefinido. Contudo, o ramo adiciona um caminho de código adicional e apresenta uma oportunidade para análise de tempo e ataque, que muitas vezes não é aceitável em software de alta integridade. Além disso, o código compila múltiplas instruções de máquina, o que é frequentemente menos eficiente do que a instrução nativa do processador.

Para evitar o comportamento indefinido e os ramos sob GCC e Clang, recomenda-se o seguinte. O padrão é reconhecido por muitos compiladores, e o compilador emitirá uma única instrução de rotação:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (-n & 31));

Existem também compiladores intrínsecos específicos do compilador que implementam mudanças circulares, como _rotl8, _rotl16, _rotr8, _rotr16 no Microsoft Visual C++. Clang fornece alguns turnos intrínsecos rotativos para compatibilidade com Microsoft que sofrem os problemas acima referidos. O GCC não oferece mudanças de rotação intrínsecas. A Intel também fornece x86 Intrinsics.

JavaEdit

Em Java, todos os tipos inteiros são assinados, pelo que os operadores “<<” e “>>” realizam turnos aritméticos. Java adiciona o operador “>>>” para efectuar turnos lógicos à direita, mas uma vez que as operações lógicas e aritméticas do turno esquerdo são idênticas para o inteiro assinado, não há operador “<<<” em Java.

Mais detalhes dos operadores de turno Java:

• Os operadores << (turno esquerdo), >> (turno direito assinado), e >>> (turno direito não assinado) são chamados os operadores de turno.
• O tipo da expressão shift é o tipo promovido do operando da esquerda. Por exemplo, aByte >>> 2 é equivalente a ((int) aByte) >>> 2.
• Se o tipo promovido do operando da esquerda for int, apenas os cinco bits da ordem mais baixa do operando da direita são utilizados como distância de deslocamento. É como se o operando da direita fosse submetido a uma lógica E operador bitwise & com o valor de máscara 0x1f (0b11111). A distância de deslocamento realmente utilizada está, portanto, sempre no intervalo 0 a 31, inclusive.
• Se o tipo promovido do operando da esquerda for longo, então apenas os seis bits da ordem mais baixa do operando da direita são utilizados como distância de deslocamento. É como se o operando da direita fosse submetido a uma lógica E operador bitwise & com o valor da máscara 0x3f (). A distância de deslocamento realmente utilizada está portanto sempre na gama 0 a 63, inclusive.
• O valor de n >>> s é n posições de bit s deslocadas para a direita com extensão zero.
• Em operações de bit e shift, o tipo byte é implicitamente convertido para int. Se o valor do byte for negativo, o bit mais alto é um, então são usados para preencher os bytes extra no int. Então byte b1 = -5; int i = b1 | 0x0200; resultará em i == -5.

JavaScriptEdit

JavaScript usa operações bitwise para avaliar cada uma de duas ou mais unidades colocadas a 1 ou 0.

PascalEdit

Em Pascal, bem como em todos os seus dialectos (tais como Object Pascal e Standard Pascal), os operadores lógicos de turno à esquerda e à direita são “shl” e “shr“, respectivamente. Mesmo para números inteiros assinados, shr comporta-se como um turno lógico, e não copia o bit do sinal. O número de lugares a mudar é dado como o segundo argumento. Por exemplo, o seguinte atribui x o resultado do deslocamento de y para a esquerda por dois bits:

x := y shl 2;