ajuda em linguagem C - deslocamento de bits

[Big Mike]

Bom pessoal, tenho um trabalho de linguagem C que envolve deslocamento de bits. Preciso fazer uma função que receba um numero de entrada qualquer, pode ser binário ou hexadecimal e quantas posições o usuário quer deslocar para esquerda ou para a direita. Ao final, o programa deverá retornar o número original deslocado n posições.

EX.:

Entrada....#posições.......Direção.......Saída

0x0001.........1...............direita........0x8000

0x0005.........2...............direita........0x4001

Sinceramente eu não sei por onde começar a resolver isso. O pior é que tenho mais 9 exercícios para fazer, este é o mais hard. Estou quebrando a cuca para fazer e não saiu nada, os outros estou quase terminando, mas esse eu não sei como fazer. Se alguém puder me ajudar, agradeço muito.

Att Big Mike

[LNW]

Big Mike,

Dê uma consultada aqui:

http://msdn.microsoft.com/pt-br/library/windowsazure/f96c63ed

http://msdn.microsoft.com/pt-br/library/windowsazure/336xbhcz%28v=vs.110%29

http://pt.wikipedia.org/wiki/Deslocamento_de_bits

Você faz esse deslocamento de bits usando o operador << (deslocamento à esquerda) ou >> (à direita)

E mais uma dúzia de textos sobre esse assunto na Net.. Google é seu amigo.

LNW

[EduardoS]

Nesse caso a operação que você precisa é "rotate" e não "shift", procurando na ent você vai ver que é fácil

[Big Mike]

ok pessoal, deixa eu entender isso, vamos pegar um exemplo:

o nº 77 deslocado uma casa para a esquerda, teríamos

0100 1101 << 1 = 1001 1010
|........................Î

ou seja, o 0 mais a esquerda passou para a direita, certo? fez o caminho contrário (desloc para a esquerda acrescenta 0 na direita)

agora, se deslocarmos uma casa para a direita, ficaria:

0100 1101 >> 1 = 0010 0110
             |...Î

neste caso, não foi simplesmente uma rotação, por que o 1, mais a esquerda do nº 77, passou ficando 0, está certo isso? como vou saber quando fica 0 ou 1? ou estou pensando errado, no caso não tem nenhuma rotação, apenas um preenchimento com 0?

agradeço ajudas

[LNW]

Mike,

neste caso, não foi simplesmente uma rotação, por que o 1, mais a esquerda do nº 77, passou ficando 0, está certo isso? como vou saber quando fica 0 ou 1? ou estou pensando errado, no caso não tem nenhuma rotação, apenas um preenchimento com 0?

agradeço ajudas

Sua observação procede, Big Mike. Na minha última mensagem eu havia ignorado aqueles valores de saída que você postou e mencionei o deslocamento simples de bits. Mas bem apontado pelo Eduardo, você realmente vai precisar de fazer uma rotação ou deslocamento circular, como queira chamar. E, neste caso sim, você vai ter o resultado esperado. Os bits serão literalmente rotacionados. Vou tentar explicar.

Para pegar a coisa simples, considere o uso de apenas 8 bits e a representação do número em hexadecimal (vou usar o número que você deu de exemplo):

Decimal: 77

Hexa: 4D

Bin: 0 1 0 0 1 1 0 1

num = 77

Ao fazer uma rotação para a direita desse número, você tem como valor final:

1 0 1 0 0 1 1 0 = A6

O que foi feito aqui?

1) Primeiro, um deslocamento de 1 bit (ou mais, caso deseje) à direita. Então, você obtém:

num >> 1

= 0 0 1 0 0 1 1 0

Mas, como você bem observou, você perde os bits que estão na ponta ao fazer esse deslocamento à direita ou esquerda, e esses mesmos bits precisam figurar sempre na outra ponta a cada deslocamento. Você precisa de alguma forma complementar esses bits perdidos na outra ponta. E complemento neste caso aqui, entenda por soma.

Número original: 0 1 0 0 1 1 0 1

Para obter o resultado final, vou precisar fazer uma operação de OU lógico (para fazer esse complemento nas pontas) com o número rotacionado à direita (primeira etapa acima) e com os bits que seriam perdidos:

Ficaria algo como:

0 0 1 0 0 1 1 0 OU

1 0 0 0 0 0 0 0

1 0 1 0 0 1 1 0 (=)

Se eu rotacionei apenas uma vez à direita, significa que perdi apenas um bit. Então, eu preciso empurrá-lo para a ponta fazendo um deslocamento de 7 bits à esquerda (8 bits total - 1 bit deslocado à direita)

num << ((total de bits, nesse caso, 8) - 1)

= 1 0 0 0 0 0 0 0

Se tivesse deslocado 5 bits à direita, precisaria compensar esses 5 bits da mesma forma, ou seja, 8 - 5 = 3.

Então:

valorfinal = (num >> 1) OU (num << (total de bits, nesse caso, 8) - 1)

= 1 0 1 0 0 1 1 0

= A6

Para rotações à esquerda, o processo é o mesmo, só que inverso nas operações acima.

Tentei ser o máximo didático.. qualquer dúvida é só postar.

LNW