operadores_bitwise.tex 12.4 KB
Newer Older
1 2 3
\documentclass[apostila.tex]{subfiles}


4 5


6
\begin{document}
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
7
\chapter{Operadores de bit}
8

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
9 10
\section{O que é uma operação bit-a-bit}

11
Uma operação bit-a-bit é, basicamente, uma operação lógica aplicada sobre cada bit de um número
12 13
inteiro.

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
14 15 16 17 18
Entende-se por operações lógicas AND, OR, NOT, XOR e SHIFT's.

Exemplo:
Tome os números $5$ e $14$. Em binário:
\begin{align}
19 20
5 &= 0101 \notag\\
14 &= 1110 \notag
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
21
\end{align}
22 23
Uma operação AND bit-a-bit entre 5 e 14:

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
24
\begin{align}
25 26 27
0101& \notag\\
1110& \notag\\
0100& \notag\\
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
28
\end{align}
29 30 31 32 33 34 35 36 37

Ou seja, 5 AND 14 = 4
Observe que a operação AND bit-a-bit realiza um AND entre os pares de bit respectivos de cada
operando.

A linguagem C suporta um conjunto completo de operadores de bit que podem ser aplicados apenas
aos tipos de números inteiros (char, int e long).

Os operadores de bit permitem que programadores possam escrever instruções de alto nível que operam
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
38 39 40 41
em detalhes de baixo nível. Por exemplo, controlar registradores de hardware ligando e desligando bits
específicos em certos endereços de memória onde estes registradores estão localizados logicamente.

\section{Representação de números hexadecimais}
42

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
43
Para os computadores, todos os dados e informações são representados em binário (base 2), porque esta
44 45 46 47 48 49 50 51
representação simplifica o projeto do hardware.

O grande problema com esta representação é que para seres humanos os dados ficam difíceis de
serem compreendidos e representados, já que mesmo números relativamente pequenos precisam de uma
quantidade muito grande de bits para serem representados.

A princípio poderia-se pensar em transformar estes números em binário em representação decimal
(base 10), já que é a representação mais natural para o ser humano. O problema de usar a base decimal
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
52
para representar números binários é que o processo de conversão é relativamente lento e altamente sujeito
53 54 55 56
a erros.

Para resolver estes problemas, a base adotada para representar dados (pelo menos em baixo nível) é a
base hexadecimal (base 16) porque representa números binários de maneira mais inteligível e a conversão
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
57
entre a base 2 e a base 16 é bastante fácil e direta.
58 59 60 61

Na linguagem C, para especificar que uma determinada constante numérica está na base hexadecimal,
basta iniciar a representação do número com 0x (zero x).

62
Exemplo:
63 64 65



66 67 68
\begin{lstlisting}
int z=0xff; // atribui a constante (ff)16 ao z.
\end{lstlisting}
69

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
70 71 72 73
\section{Operações bit-a-bit em C}

\begin{table}
	\centering
74
	\begin{tabular}{|p{.13\textwidth}|p{.13\textwidth}|p{.74\textwidth}|}
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
		\hline Operador & Nome 	& Descrição \\
		\hline \verb|&| & AND	& E binário \\
		\hline \verb\|\ & OR	& OU binário \\
		\hline \verb\^\ & XOR	& OU EXCLUSIVO binário \\
		\hline \verb\<<\ & SHIFT LEFT	& Desloca todos os bits uma posição para esquerda \\
		\hline \verb\>>\ & SHIFT RIGHT	& Desloca todos os bits uma posição para direita \\
		\hline \verb\~\ & NOT	& Complemento ou negação, $1$'s viram $0$'s e $0$'s viram $1$'s  \\
		\hline
	\end{tabular}
	\caption{Operadores de bits existentes em C}
\end{table}

Em expressões, os operadores AND (\verb|&|), OR (\verb\|\) e XOR (\verb|^|) combinam valores de acordo com as regras
para seus equivalentes lógicos. Deve-se tomar cuidado para não confundir os operadores de bit \verb\&\ e \verb\|\
com os operadores lógicos \verb\&&\ e \verb\||\. Da mesma forma com o que acontece com os operadores \verb\=\ e \verb\==\, a
90 91
linguagem C permite que usemos o operador errado em muitos casos sem apontar o erro.

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
92
\section{Operador \& (AND)}
93

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
94
O operador \verb\&\ executa uma operação E (AND) lógica em cada um dos bits dos operandos. Observe o
95 96 97 98 99 100 101 102 103 104 105 106
quadro na figura \ref{tab:and}.

\begin{table}[htb]
\centering
\begin{tabular}{lrl|l|l}
0 \verb\&\ 0 = 0 &  Ex: & Dec.  &  Hex.  & Binário \\
0 \verb\&\ 1 = 0 &      & 31503 & 0x7b0f & 0111 1011 0000 1111 \\
1 \verb\&\ 0 = 0 & \verb|&| & 16277 & 0x3f95 & 0011 1111 1001 0101 \\
1 \verb\&\ 1 = 1 &      & 15109 & 0x3b05 & 0011 1011 0000 0101 \\
\end{tabular}
\caption{Regras do Operador \&}\label{tab:and}
\end{table}
107

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
108
À esquerda temos a tabela-verdade para o operador \verb\&\ : o bit de resultado é 1 somente quando ambos
109 110
os bits dos operandos forem 1.

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
111
À direita é exibido um exemplo de uma operação AND. Tanto os operandos
112

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
113
quanto o resultado são exibidos em três bases: decimal, hexadecimal e binária.
114

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
115
Vale a pena ressaltar que, quando bits são manipulados, a base decimal não é muito apropriada para
116 117
a representação. Ao invés da base decimal, utiliza-se a base hexadecimal.

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
118
Um uso típico do operador \verb\&\ é mascarar parte de um número, ou seja, permitir que apenas uma parte
119 120 121 122 123 124
desse número seja utilizada para um determinado fim.

Suponha que uma determinada variável VAR A represente a configuração de um programa.
Cada bit desse número representa o estado ativado(1)/desativado(0) para uma determinada opção do
programa.

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
125 126
Se deve ser escrito um algoritmo para detectar se a opção associada ao 3º 
bit está ativada, pode ser utilizado um AND de bits da seguinte forma:
127

128 129 130
\begin{lstlisting}
A & 4 // 4 em binário é (100)2
\end{lstlisting}
131

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
132
O resultado desta operação só será diferente de zero se o 3º bit estiver ativado.
133

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
134
\section{Operador | (OR)}
135

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
136 137
O operador \verb\|\ executa uma operação OU (OR) entre cada bit dos operandos. As regras lógicas que definem
o operador \verb\|\ determinam que se pelo menos um dos bits for 1, então o bit do resultado será 1. No caso
138 139
de ambos os bits serem 0, o resultado será 0.

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
140
O operador \verb\|\ pode ser utilizado para ligar (setar) bits em números.
141

142 143 144 145 146 147 148 149 150 151
\begin{table}
\centering
\begin{tabular}{lrl|l|l}
0 | 0 = 0 & Ex: & Dec. & Hex. & Binário \\
0 | 1 = 1 &     & 31503 & 0x7b0f & 0111 1011 0000 1111 \\
1 | 0 = 1 &   | & 16277 & 0x3f95 & 0011 1111 1001 0101 \\
1 | 1 = 1 &     & 32671 & 0x7f9f & 0111 1111 1001 1111 \\
\end{tabular}
\caption{Regras para o operador |}
\end{table}
152 153

Considerando novamente o exemplo da variável VAR A que determina a configuração de um programa,
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
154
suponha que seja necessário ativar o 3º bit. Para tanto, a seguinte operação pode ativar o 3º bit:
155

156 157 158 159
\begin{lstlisting}
A | 4 // 4 em binário é 100
\end{lstlisting}

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
160 161
Ou seja, como pelo menos o 3º bit da constante 4 é 1, isso significa que o resultado da operação 
terá o 3º bit com o valor 1.
162

163
\section{Operador \^\ (XOR)}
164

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
165
O operador \verb\^\ executa uma operação OU EXCLUSIVO (XOR) entre cada um dos bits dos operandos.
166 167
Genericamente, dados n operandos, o resultado de uma operação XOR entre os n operandos será 1 se, e
somente se, o número de operandos que assumem valor 1 é impar.
168 169
\\
\begin{table}[htb]
170
\centering
171
\begin{tabular}{lrl|l|l}
172 173 174 175 176 177 178
0 \verb\^\ 0 = 0 &      Ex: & Dec.  &  Hex.  & Binário \\
0 \verb\^\ 1 = 1 &          & 31503 & 0x7b0f & 0111 1011 0000 1111 \\
1 \verb\^\ 0 = 1 & \verb\^\ & 16277 & 0x3f95 & 0011 1111 1001 0101 \\
1 \verb\^\ 1 = 0 &          & 17562 & 0x449a & 0100 0100 1001 1010 \\
\end{tabular}
\caption{Regras para o operador $\hat{}$ }
\end{table}
179

180
Na esquerda do quadro é exibida a tabela verdade que define a operação e à direita um exemplo mostrado
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
181
nas três bases mais usadas.
182 183

A operação XOR possui uma propriedade interessante: se uma máscara é aplicada duas vezes ao
184
mesmo número, o resultado é o número original. De uma forma genérica, podemos dizer que $(A\hat\ B)\hat\ B = A$.
185

186
A tabela \ref{tab:xor_transi} demonstra esta propriedade.
187

188 189 190 191 192 193 194 195 196 197 198 199 200
\begin{table}
\centering
\begin{tabular}{rl|l|l}
         & Dec.  &  Hex.  &      Binário \\ \hline
         & 31503 & 0x7b0f & 0111 1011 0000 1111 \\
$\hat{}$ & 16277 & 0x3f95 & 0011 1111 1001 0101 \\ \cline{2-4}
         & 17562 & 0x449a & 0100 0100 1001 1010 \\ \cline{2-4}\cline{2-4}
         & 17562 & 0x449a & 0100 0100 1001 1010 \\
$\hat{}$ & 16277 & 0x3f95 & 0011 1111 1001 0101 \\\cline{2-4}
         & 31503 & 0x7b0f & 0111 1011 0000 1111 \\
\end{tabular}
\caption{Propriedade especial do XOR}\label{tab:xor_transi}
\end{table}
201

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
202 203
Esta propriedade torna a operação XOR bastante usada em criptografia. Aplica-se uma máscara sobre
um documento através de um XOR e obtém-se o documento ``disfarçado''. Reaplicando-se a máscara,
204 205 206 207
obtém-se de volta o documento original. Naturalmente, só isso não garante uma criptografia segura,
mas muitos algoritmos sofisticados de criptografia ainda fazem uso dessa capacidade especial do XOR
misturada com outras técnicas.

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
208 209 210
\section{Operadores << e >>}
Os operadores de deslocamento para a esquerda (shift left - \verb\<<\) e de deslocamento para a direita (shift
right - \verb\>>\) movimentam (empurram) os bits para a esquerda e direita, respectivamente.
211 212

A forma geral de uso desses operadores é:
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
213 214 215 216 217
\begin{verbatim}
[valor] >> [número de posições]
[valor] << [número de posições]
\end{verbatim}

218 219
Observe o exemplo abaixo:

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
220
\begin{lstlisting}
221 222 223 224
// ... 
unsigned int x = 0xC743; // x = 1100 0111 0100 0011 
x = x << 3; // x = 0011 1010 0001 1000 
// ... 
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
225
\end{lstlisting}
226 227 228

Observe que os bits de x foram empurrados 3 posições para a esquerda. Os 3 bits mais significativos de
x são perdidos e os 3 bits menos significativos passam a valer 0. No deslocamento para a direita, o processo
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
229
é semelhante, porém os bits menos significativos é que são perdidos, enquanto zeros são introduzidos nos 
230 231
bits mais significativos.

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
232
Convém ressaltar que os deslocamentos não são rotações, ou seja, os bits que saem de um lado não
233 234
retornam pelo outro.

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
235 236
Os operadores de deslocamento também podem ser usados para realizar multiplicação ou divisão
rápida de inteiros. Um deslocamento de 1 bit à esquerda equivale a multiplicar o número por 2. Já um
237 238
deslocamento de 1 bit para a direita equivale a dividir o número por 2. Genericamente, temos:

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
239
\begin{lstlisting}
240 241
x = x << n; // equivalente a: x = x * 2^n; 
x = x >> n; // equivalente a: x = x / 2^n; 
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
242 243
\end{lstlisting}

244
\section{Operador \texttildelow{} (complemento)}
245

246
O operador \texttildelow{} (complemento) é um operador unário, isto é, trabalha com somente um operando, que é
247 248 249
colocado após o símbolo do operador, assim como o operador ! (NOT).

A sua função é calcular o complemento do valor fornecido, ou seja, trocar todos os bits 0 por 1 e todos
250
os bits 1 por 0. Assim como todos os outros operadores, o operador \texttildelow{} não altera o valor do operando, o que
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
251
significa que o resultado da operação deve ser atribuído a uma variável ou utilizado em uma expressão.
252

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
253
\begin{lstlisting}
254
unsigned int v1, v2;
255 256
v1 = 0x7f4a; // v1 = 0111 1111 0100 1010 
v2 = ~v1; // v2 = 1000 0000 1011 0101 
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
257
\end{lstlisting}
258

259
\section*{Exercícios}
260 261 262 263 264 265 266 267 268

1. Escreva um programa que imprime duas perguntas simples com resposta de múltipla escolha através
de somatório. O programa deverá receber a resposta do usu'ario (que ser'a um número) e dever'a
apresentar na tela a pontuação de acordo com o nível do acerto.

O programa deverá imprimir o seguinte enunciado:
Para responder as perguntas abaixo, verifique quais as alternativas que voce considera corretas, some
o numero da alternativa e escreva essa soma como resposta.

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
269
As perguntas e suas respectivas alternativas devem ser:
270

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
271
\begin{verbatim}
272 273 274 275 276 277 278 279 280 281 282 283 284 285 286
Quais funções abaixo pertencem a biblioteca stdio.h da linguagem C?
1) write
2) printf
4) getchar
8) cos
16) scanf
Resposta:[2+4+16=22]

Quais os tipos de dados são pré-definidos na linguagem C?
1) int
2) longint
4) long int
8) char
16) string
Resposta:[1+4+8=13]
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
287
\end{verbatim}
288 289 290 291

Os números entre [ ] apresentam o somatório das opções corretas.
Os resultados deverão ser avaliados de acordo com a seguinte tabela:

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
292
opções corretas/total pontuação texto a imprimir na tela
293 294 295 296
1/3 1 Voce esta fraco.
2/3 3 Continue assim.
3/3 5 Parabéns!

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
297
Caso exista pelo menos uma opção incorreta, a pontuação deverá ser 0 e o programa deverá imprimir
298 299
uma mensagem avisando que o usuário errou uma das respostas.

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
300 301
O valor digitado pelo usuário deverá ser comparado com um gabarito, que serão valores guardados
em um pequeno vetor ( de 2 posições).
302 303

2. Faça um programa que recebe um número(em decimal) e imprime o seu valor em binário. O
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
304
programa só poderá utilizar operações lógicas.
305

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
306 307
3. Crie duas funções denominadas rot left (int s) e rot right (int s) que realizem as rotações, para
esquerda e direita respectivamente, de seu parâmetro e retorne esse valor.
308 309 310 311

Suponha que a rotação será sobre um número de 16 bits.
Abaixo, ilustramos o efeito de rotações:

Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
312
\begin{lstlisting}
313
var x = 18 // 18 é (10011)2 em binário 
Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
314 315 316
rot_left(x) = 00111
rot_right(x) = 11001
\end{lstlisting}
317 318


Jomaro Rodrigues's avatar
Jomaro Rodrigues committed
319
Uma rotação empurra o bit que sumiria para o lado oposto.
320 321

\end{document}