Seu navegador não oferece leitura em voz alta. Você pode ler o guia normalmente.
Por trás de tudo o que um computador faz estão operações lógicas sobre bits. Em provas, elas aparecem de três formas: a tabela-verdade de uma porta, a operação bit a bit entre dois números binários e o cálculo do endereço de rede com a máscara. As três usam as mesmas regras, e todas são verificáveis. Este guia traz as tabelas, três exemplos resolvidos e conferidos por programa e as pegadinhas.
Sem norma aplicável: é fundamento de computação. A lógica proposicional, com os mesmos conectivos, é tratada em proposições e tabela-verdade.
As portas básicas
Cada porta recebe um ou dois bits e devolve um bit. As tabelas para entradas A e B:
| A | B | AND | OR | XOR | NAND | NOR |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
E a porta NOT, que inverte o bit: NOT 0 = 1 e NOT 1 = 0.
Como memorizar:
- AND (E): só dá 1 se todas as entradas forem 1.
- OR (OU): dá 1 se pelo menos uma entrada for 1.
- XOR (OU exclusivo): dá 1 se as entradas forem diferentes.
- NAND: é o AND seguido de NOT; dá 0 só quando as duas entradas forem 1.
- NOR: é o OR seguido de NOT; dá 1 só quando as duas entradas forem 0.
A diferença entre OR e XOR está na linha 1 e 1: o OR dá 1; o XOR dá 0. É a pegadinha mais comum.
Operações bit a bit
Quando as portas atuam sobre números inteiros, a operação é feita posição por posição, em cada par de bits. Sejam x = 10110110 e y = 11001010 (8 bits).
| Operação | Resultado |
|---|---|
| x AND y | 10000010 |
| x OR y | 11111110 |
| x XOR y | 01111100 |
| NOT x | 01001001 |
Confira a primeira posição (a mais à esquerda): x tem 1 e y tem 1; AND dá 1, OR dá 1 e XOR dá 0. Na segunda posição: x tem 0 e y tem 1; AND dá 0, OR dá 1, XOR dá 1. E assim sucessivamente.
Deslocamentos
Deslocar bits para a esquerda uma posição, descartando o excedente e completando com zero à direita, multiplica o número por 2 (enquanto não houver estouro). Deslocar para a direita divide por 2, descartando o resto. Com x = 10110110, o deslocamento de um bit à esquerda em 8 bits dá 01101100 (o bit mais à esquerda se perde), e o deslocamento de dois bits à direita dá 00101101.
Uso 1: máscara para achar o endereço de rede
O endereço da rede se obtém com um AND bit a bit entre o endereço IP e a máscara. O endereço de difusão (broadcast) se obtém com OR entre o IP e o inverso da máscara.
Exemplo resolvido
Qual é o endereço de rede e o de broadcast do host 192.168.10.77 com a máscara 255.255.255.192 (prefixo /26)?
- Só o último octeto é interessante, pois os três primeiros têm máscara 255 (AND com 255 mantém o valor): 192.168.10.
- Último octeto: 77 em binário é 01001101; 192 é 11000000.
- AND: 01001101 AND 11000000 = 01000000, que é 64.
- Endereço da rede: 192.168.10.64.
- Inverso da máscara no último octeto: 00111111 (63).
- OR: 01001101 OR 00111111 = 01111111, que é 127.
- Endereço de broadcast: 192.168.10.127.
Conferência: o bloco /26 tem 64 endereços (2^6). A rede começa em 64 e vai até 127; o host 77 está dentro. Para planejar blocos, veja endereçamento IPv4 e CIDR e VLSM.
Uso 2: XOR e criptografia simples
O XOR tem uma propriedade importante: aplicar a mesma chave duas vezes devolve o original. Com a mensagem 1011 e a chave 0110: 1011 XOR 0110 = 1101; aplicando de novo a chave, 1101 XOR 0110 = 1011. Essa reversibilidade é o princípio de cifras simples e aparece em esquemas de paridade, como no RAID. Para a criptografia moderna, veja chaves simétricas e assimétricas.
Uso 3: máscaras de bits e permissões
Um AND com uma máscara isola bits de interesse: AND com 00001111 mantém os quatro bits menos significativos e zera os demais. Um OR com uma máscara liga bits: OR com 00000100 coloca o terceiro bit em 1. Um XOR com uma máscara inverte os bits marcados. As permissões de arquivo em Linux (leitura, escrita e execução) são um exemplo prático de bits ligados e desligados; veja chmod em notação octal.
Álgebra booleana: equivalências úteis
Valem as leis de De Morgan para portas: NOT(A AND B) = (NOT A) OR (NOT B), e NOT(A OR B) = (NOT A) AND (NOT B). O NAND é, assim, equivalente a “NOT A OR NOT B”. Em negação de proposições e De Morgan o mesmo raciocínio aparece na lógica proposicional. Outra propriedade: NAND e NOR são chamadas portas universais, pois qualquer outra porta pode ser construída apenas com um desses tipos.
Pegadinhas
- Confundir XOR com OR na entrada 1 e 1.
- Esquecer que o NAND e o NOR são o AND e o OR invertidos.
- Fazer operação bit a bit sem alinhar os números pela direita.
- Calcular a rede com OR em vez de AND.
- Confundir operação lógica com operação aritmética (somar bits).
Próximos passos
Veja complemento de dois e tabela-verdade: treino comentado.
Fontes e atualização
Sem norma aplicável. Tabelas e operações conferidas por programa. Confira o edital para ver o que a banca inclui em arquitetura e lógica digital. Veja a metodologia do site.