Jump to content
gnoo

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

Recommended Posts

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.

 

 

Captura de ecrã_2019-02-22_14-49-23.png

 

 

Exemplo com shift left

Imaginando o seguinte exemplo

 

990187419_Capturadeecr_2019-02-22_15-11-30.png.0be036bbcca51ba196d48d649e2f33da.png

 

Raciocínio:

1162178581_Capturadeecr_2019-02-22_15-34-09.png.77479dc26d6bb7c3a4c8d5e66e3d0589.png

Que é o mesmo que….

866749130_Capturadeecr_2019-02-22_15-40-53.png.0bfbff425d6d7828e2c0ae9a13734ad6.png

 

 

Exemplo com shift right

1095527822_Capturadeecr_2019-02-22_18-13-45.png.0e338555e62fd7d63603a67d5b631222.png

Raciocínio

1505477576_Capturadeecr_2019-02-22_22-12-42.png.194fd3df9b6d9e005b023c33cc98c84f.png

 

Que é o mesmo que…

891281243_Capturadeecr_2019-02-22_22-17-05.png.ba5b944aabea5ba98447d550be5428a2.png

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

992982317_Capturadeecr_2019-02-22_22-29-23.png.25d2abf699b7404b6ccae177b7b32c8c.png

 

É 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.

 

 

 

Edited by gnoo
  • Agradecer 2

Share this post


Link to post
Share on other sites

@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.

  • Agradecer 1

Share this post


Link to post
Share on other sites

@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.

Edited by gnoo

Share this post


Link to post
Share on other sites

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).
 

Edited by fredericopissarra
  • Agradecer 2

Share this post


Link to post
Share on other sites

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...

  • Agradecer 1

Share this post


Link to post
Share on other sites

@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.

Edited by gnoo

Share this post


Link to post
Share on other sites
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".

Edited by fredericopissarra

Share this post


Link to post
Share on other sites

@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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...