Como entender / calcular - operadores bitwise shift right & shift left

[Visitante gnoo]

Saudações,

 

quando começamos a mexer com operadores bitwise, não é difícil encontrar conteúdo que nos serve como exemplo, mas há alguns pormenores que nos pode ajudar a estruturar um raciocínio na altura de manipular bits que nunca são referidos, neste caso vou deixar aqui uma ideia que nos podem ajudar a usar os operadores shift left e shift right.

Os exemplos que vou deixar são feitos com python, mas o conceito é o mesmo para outras linguagens programação.

Conceito básico de POTÊNCIA ( matemática)

Potência é uma multiplicação onde se repete sempre o mesmo fator.

 

 

 

 

Exemplo com shift left

Imaginando o seguinte exemplo

 

 

Raciocínio:

Que é o mesmo que….

 

 

Exemplo com shift right

Raciocínio

 

Que é o mesmo que…

Quando o resultado do shift right é um número decimal

Quando o número do resultado do shift right é um número decimal o número perde as casas decimais sendo apenas representado por um número inteiro. Imaginando que temos 5 >> 1, em que 5 é dividido por 2 elevado a 1 ( que é 2, sendo que todos os números elevados a 1 representam o mesmo número ), então 5 : 2 = 2,5

Mas o resultado vai ser 2, é sempre representado por um número inteiro, vamos ver na prática

 

É claro que o que está por trás disto é um pouco mais complexo, mas acho que esta abordagem é interessante na altura de pensar uma solução para o nosso problema.

Abraço.

 

 

 

[trevizan]

@gnoo, muito bom. 

É importante entender as operações de shift, principalmente se estiver implementando funções matemáticas/criptográficas para dispositivos com restrição de processamento, como boa parte dos microcontroladores que tem como uma das características o baixo consumo de energia.

[Visitante gnoo]

@trevizan Obrigado espero que seja útil. :)

Não sei se este exemplo chega para implementar funções matemáticas/criptográficas, mas se for o inicio de algo já é bom.

[fredericopissarra]

A analogia com a divisão (no caso de shifts para a direita) não é totalmente correta... Em C/C++, quando o operando do lado esquerdo (o dado a ser deslocado) é negativo a operação de shift para a direita é "dependente de implementação". Existem dois tipos de shifts: Um "shift lógico" e um "shift aritmético". No caso de shifts para a direita, a variante "lógica" sempre complementa o dado com 0, já a variante aritmética copia o bit de mais alta ordem (MSB) original no novo MSB. Eis o porquê:

Considerando apenas 8 bits (para não usar números binários muito grandes, mas a explicação vale para valores maiores também), o valor -4 é expresso, em binário, como 0b11111100. Se usarmos um "shift lógico" para a direita um '0' é colocado no MSB, ou seja, -4 >> 1 = 0b11111100 >> 1 = 0b01111110. Esse valor, em decimal é +126, que não lembra em nada uma divisão por 2.

Mas, se usarmos um "shift aritmético" para a direita, é feita uma cópia do MSB no novo MSB, ou seja, 0b11111100 >> 1 = 0b11111110, que, em complemento 2, é -2, obtendo exatamente o a divisão por 2. Mas, tem um problema: -1 >> 1 = -1! Ou seja, 0b11111111 >> 1 = 0b11111111! Não houve "divisão alguma"!

Em C, shifts para direita com operador sinalizado é "dependente de implementação" porque o compilador pode usar um dos dois tipos de shifts... Isso não acontece se o operador for 'unsigned', onde o shift lógico é sempre usado.

Em Python o shift "aritmético" é sempre usado:

>>> -1 >> 1
-1

Ainda outro detalhe: O operando à direita (a quantidade de bits do deslocamento) não pode ser negativa. Você poderia pensar que um deslocamento negativo mudaria o sentido do mesmo, mas esse valor é inválido. Em C/C++ isso é um "undefined behavior", e provavelmente um erro, mas em Python isso é, definitivamente, um erro:

>>> 10 >> -2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: negative shift count

Em minha experiência, ao usar deslocamentos negativos os compiladores C/C++, no máximo, avisam do problema... Mas, se o deslocamento vier de uma variável, ele simplementes não é feito (é como se fosse "deslocar zero bits").

Reparem que os problemas surgem com shifts para direita apenas (e com deslocamentos negativos para ambos os lados). Isso porque shifts para a esquerda sempre são "lógicos" e nunca "aritméticos". Em assembly, x86, temos as instruções SHR (SHift "logical" to Right) e SAR (Shift Arithmetic to Right)... E também temos SHL e SAL (mas essas duas são a mesma instrução, pelo motivo que expliquei acima).
 

[fredericopissarra]

Para complementar, a analogia com a multiplicação, nos deslocamentos à esquerda, também não funcionam em todos os casos... Considerando apenas 8 bits, se deslocarmos 0b01111111, ou seja, o valor +127, para a esquerda em 1 bit, teremos 0b11111110, que em valor sinalizado nos dá -2.

Claro que esse é um caso de overflow e o flag OF será setado, mas em C não temos como investigar os flags... Pelo menos não em uma operação desse tipo...

[Visitante gnoo]

@fredericopissarra realmente eu não tinha pensado nisto com número negativos, obrigado por  lembrares esse pormenor.

Só não percebi o reparo que fazes na multiplicação, quando dizes que 127 positivo com um 1 bit para a esquerda o resultado é  -2, eu estou a tentar fazer isso e obtenho um resultado diferente, podes fazer um script a demonstrar isso? 

Obrigado.

[fredericopissarra]

1 hora atrás, gnoo disse:

@fredericopissarra realmente eu não tinha pensado nisto com número negativos, obrigado por  lembrares esse pormenor.

Só não percebi o reparo que fazes na multiplicação, quando dizes que 127 positivo com um 1 bit para a esquerda o resultado é  -2, eu estou a tentar fazer isso e obtenho um resultado diferente, podes fazer um script a demonstrar isso? 

Obrigado.

O exemplo que dei foi baseado no tipo char, que é sinalizado e tem 8 bits de tamanho... No caso de Python, ele usa aritmética de múltipla precisão para fazer seus cálculos. Assim, você pode fazer shifts para a esquerda com quantos bits quiser:

>>> 1 << 1024
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216L

Eis um programinha em C que exemplifica o que eu disse:

#include <stdio.h>

void main( void )
{
  char n = 127, m;

  m = n << 1;
  printf( "%d shl 1 = %d\n", n, m );
}

Compile e execute. Você verá "127 shl 1 = -2".

[Visitante gnoo]

@fredericopissarra eu quando fiz este post fiz a pensar em dados do tipo inteiro, e realmente não pensei além disso o que talvez tenha sido um erro, tanto não pensei em números negativos como também não pensei em valores do tipo char, qualquer das formas ficou bem claro que existem algumas variáveis neste tipo de abordagem. Obrigado.

[fredericopissarra]

34 minutos atrás, gnoo disse:

@fredericopissarra eu quando fiz este post fiz a pensar em dados do tipo inteiro, e realmente não pensei além disso o que talvez tenha sido um erro, tanto não pensei em números negativos como também não pensei em valores do tipo char, qualquer das formas ficou bem claro que existem algumas variáveis neste tipo de abordagem. Obrigado.

Valeu... É um erro comum pensar em shifts como multiplicações e divisões rápidas por potências de dois. Esse tipo de pensamento é válido desde que os operandos sejam 'unsigned' e o deslocamento não exceda o tamanho, em bits, do operando à esquerda... Nesse caso, a analogia é perfeita.

Eu só chamei a atenção para esses fatos porque se alguém toma a regra da "divisão rápida" ou "multiplicação rápida" como inegável, poderá obter um "bug", com as exceções que citei, que dificilmente irá achar. Acho que é bom que, quando queremos realizar divisões por potência de dois usemos o operador '/', mesma coisa com multiplicações (com o operador '*'). Somente com casos onde seja impossível quebrar as regras é que os operadores '<<' e '>>' deveriam ser usados.

Aliás... Em python esse tipo de atalho não faz muito sentido, já que, como fica evidente nos testes, ele usa aritmética de múltipla precisão que, por definição, é bem mais lenta que a aritmética binária usada em processadores. Em linguagens compiladas (C e C++, por exemplo) a diferença em ciclos pode ser muito grande (multiplicações gastam 5 ciclos, divisões uns 20 ou 30, mas shifts apenas 1).

[]s
Fred

[Visitante gnoo]

@fredericopissarra devias fazer um artigo sobre isso, porque encontramos muita informação mas com esse nível de análise é difícil 

[fredericopissarra]

Tenho algum material pronto (livros), mas estou reescrevendo para publicação:

https://drive.google.com/open?id=0B0CaWSBeZmmKQ0FCZ1g5VGk0cVk

https://drive.google.com/open?id=0B0CaWSBeZmmKRkFRcVoxMGUxYXc

Esses ai são públicos e distribuíveis...

[[]]ão
Fred