Computadores são empregados atualmente nas mais diversas atividades, como edição e composição de textos, sons e imagens, mecanização e automatização de diversas tarefas, simulação dos mais variados fenômenos e transferência de grandes volumes de informação entre locais possivelmente muito distantes. Seu uso em atividades científicas permitiu transpor inúmeras fronteiras, assim como criar novas e desafiantes áreas de investigação.
Como se pode explicar tão grande impacto? O que diferencia um computador de uma ferramenta qualquer?
De fato, o conjunto das operações básicas executadas por um computador é tão simples quanto o de uma pequena calculadora. A grande distinção de um computador, responsável por sua enorme versatilidade, está no fato dele ser programável. Computadores podem realizar tarefas complexas pela combinação de suas operações básicas simples. Mas, como isso é possível? Como podemos descrever para o computador a tarefa que queremos que ele execute?
Para que um computador possa executar qualquer tarefa, é preciso que lhe seja fornecida uma descrição, em linguagem apropriada, de como essa tarefa deve ser realizada. Tal descrição é chamada de programa e a linguagem usada para essa descrição, de linguagem de programação. A idéia ou processo que esse programa representa é chamada de algoritmo.
Algoritmo e programa não são noções peculiares à computação. Um algoritmo consiste simplesmente em uma descrição finita de como realizar uma tarefa ou resolver um problema. Essa descrição deve ser composta de operações executáveis. Cozinhar, montar móveis ou briquedos, realizar cálculos matemáticos ou tocar um instrumento musical, são exemplos de tarefas que podem ser executadas usando um algoritmo. Receitas de cozinha, instruções de montagem, regras para realização de cálculos e partituras musicais são exemplos de programas (representações de algoritmos) para realizar essas tarefas.
A distinção entre algoritmo e programa é similar à distinção existente, por exemplo, entre número e numeral. Essa distinção muitas vezes não se faz perceber, por se tornar dispensável. Por exemplo, não escrevemos “número representado por 7” ou “número denotado por 7”, mas simplesmente “número 7”. É útil saber, no entanto, que podem existir diversas denotações para um mesmo algoritmo, assim como um número pode ser escrito de diferentes maneiras, tais como:
| 7 | VII | sete | seven | ||||||| |
Embora seja capaz de executar apenas um pequeno número de operações básicas bastante simples, um computador pode ser usado, em princípio, para resolver qualquer problema cuja solução possa ser obtida por meio de um algoritmo. O segredo é que um computador provê também um conjunto de instruções para a combinação dessas operações que, embora também reduzido, é suficiente para expressar qualquer algoritmo. Essa tese, de que o conjunto de operações básicas e instruções de um computador é suficiente para expressar qualquer algoritmo, constitui uma tese resultante de trabalhos com modelos computacionais distintos usados nas primeiras pesquisas teóricas em computação, que se mostraram equivalentes, em termos de o que se poderia computar com eles. Essas pesquisas lançaram as bases para a ciência da computação e para a construção dos primeiros computadores (ver Notas Bibliográficas (1.6)).
Como construir algoritmos para a solução de problemas e como expressar tais algoritmos de modo adequado usando uma linguagem de programação constituem os temas centrais deste livro. Entretanto, faremos agora um pequeno preâmbulo para estudar brevemente as bases da organização e o funcionamento de um sistema de computação. Esse conhecimento nos permitirá entender como o computador executa os nossos programas.
A atual tecnologia de construção de computadores é baseada em dispositivos eletrônicos que são capazes de distinguir, com precisão, entre dois estados diferentes de um sinal elétrico, caracterizados comumente pelos símbolos 0 e 1. Devido a essa característica, dados e operações são representados, em um computador, em uma linguagem que tem apenas esses dois símbolos, isto é, uma linguagem binária. Cada um desses símbolos é comumente chamado de bit (do inglês binary digit).
Apesar do extraordinário avanço da atual tecnologia de construção de computadores, todo computador moderno mantém uma organização básica semelhante. Essa organização é mostrada na Figura 1.1 e seus componentes principais são descritos brevemente a seguir.
Figura 1.1: Organização básica de um computador
O processador, também chamado de unidade central de processamento (em inglês, CPU — Central Processing Unit), é o componente do computador que executa as instruções de um programa, expresso em uma linguagem que ele pode entender. Durante a execução de um programa, o processador “lê” a instrução corrente, executa a operação especificada nessa instrução e determina qual é a próxima instrução do programa que deve ser executada. Isso se repete até a execução de uma instrução que indica o término do programa.
Muitas dessas instruções precisam de um lugar de onde tirar os operandos e onde armazenar temporariamente os resultados. Operandos e resultados são chamados em computação de valores, ou dados: são sequencias de bits que podem representar um número, ou um caractere, ou outro valor qualquer. O lugar que armazena um operando de uma instrução em um computador é chamado de registrador. Podemos ver um registrador como uma caixinha, cada uma com um nome distinto, que armazena apenas um valor de cada vez.
Outro componente do computador é a memória principal, em geral chamada simplesmente de memória, ou RAM (do inglês Random Access Memory). A memória é usada para armazenar os programas a serem executados pelo computador e os dados manipulados por esses programas. Essa característica de utilizar um único dispositivo de memória para armazenar tanto programas quanto dados, peculiar a todos os computadores modernos, é distintiva da chamada arquitetura de von Neumann, assim denominada em homenagem ao pesquisador alemão que originalmente publicou artigo sobre essa arquitetura, em 1946.
A memória do computador consiste em uma seqüência finita de unidades de armazenamento de dados, cada qual identificada pelo seu endereço, isto é, por um número inteiro não-negativo que corresponde à sua posição nessa seqüência. Cada unidade de armazenamento de dados da memória é comumente chamada de uma palavra. Uma palavra de memória usualmente é composta de um pequeno número de bytes (em geral, 4 ou 8). Cada byte armazena uma sequência de 8 bits.
O outro grupo de componentes do computador é constituído pelos seus dispositivos de entrada e saída, também chamados de dispositivos periféricos (ou apenas de periféricos). Os periféricos são usados para a comunicação de dados entre o computador e o mundo externo. O teclado e o mouse são exemplos de dispositivos de entrada. A tela, ou monitor, e a impressora são exemplos de dispositivos de saída. Alguns dispositivos, como discos e pendrives, constituem dispositivos tanto de entrada quanto de saída de dados.
A linguagem constituída pelas instruções que podem ser diretamente executadas por um computador, representadas na forma de sequências de bits, é chamada de linguagem de máquina.
A linguagem de máquina de um computador consiste das instruções que seu processador é capaz de executar. Elas são instruções para realizar a execução de operações básicas, tais como somar dois números ou comparar se dois números são iguais, transferir dados entre a memória e um registrador, ou entre a memória e um dispositivo de entrada e saída, desviar a execução de um programa para uma instrução armazenada em um dado endereço. Um processador é capaz de processar sequências de bits, e portanto um programa escrito em linguagem de máquina deve ser uma sequência de bits.
A característica de linguagens de máquina que faz com que um processador seja capaz de executar instruções de programas escritos nessas linguagens é que existe um código único para cada instrução que determina o tamanho dos operandos e do resultado da operação. Ao ler e decodificar o código de cada instrução, o processador pode iniciar a leitura de cada operando e comandar a execução da operação necessária, e armazenar o resultado no lugar designado pelo código.
Vejamos um exemplo. Vamos considerar um fragmento de uma linguagem de máquina que contém, dentre o conjunto de instruções dessa linguagem, as seguintes instruções:
Vamos escrever um programa para somar dois números, sendo que um deles é igual a 5 e o outro está guardado, previamente, na memória do computador no endereço BBEh (3006 em decimal). Suponhamos que, dentre o conjunto de registradores da nossa máquina, há dois registradores R1 e R2, que correspondem aos códigos 00 e 01 respectivamente. Nosso programa irá, um pouco mais detalhadamente:
O código de cada uma dessas instruções é mostrado, na segunda coluna, a seguir.
| Operação | Código | |
| CARREGAR valor inteiro em registrador | 0000 | |
| CARREGAR valor em memória em registrador | 0001 | |
| SOMAR valor em registrador com valor em | 0010 | |
| registrador e guardar resultado no primeiro registrador | ||
| DESVIAR execução se resultado de | 0011 | |
| instrução anterior for maior ou igual a zero |
O trecho de programa é mostrado, na terceira coluna, a seguir.
| Localização | Operação | Sequência de bits |
| 0x00e3 | CARREGAR #5 em R1 | 0000 000000000101 000000000000 |
| 0x00e4 | CARREGAR em R2 valor armazenado | 0001 101110111110 000000000001 |
| no endereço BBEh (3006) | ||
| 0x00e5 | SOMAR R1 com R2 e | 0010 000000000000 000000000001 |
| guardar resultado em R1 | ||
| 0x00e6 | DESVIAR para endereço 0x00e5 se | 0011 000011100011 000000000000 |
| resultado da instrução anterior for | ||
| maior ou igual a zero |
Essa sequência de bits poderia ser um pequeno trecho de um programa escrito em linguagem de máquina. Como já mencionamos, tais programas consistem em instruções muito básicas, tais como somar dois números, ou comparar se dois números são iguais, ou transferir dados entre a memória e um registrador, ou entre a memória e um dispositivo de entrada e saída, e controlar o fluxo de execução das instruções de um programa.
Na época em que foram construídos os primeiros computadores, os programadores usavam instruções como essas, cada qual formada por aproximadamente uma dezena de bits, para descrever seus algoritmos. Programar nessa linguagem era uma tarefa trabalhosa e extremamente sujeita a erros, difíceis de detectar e corrigir, que geravam programas difíceis de serem estendidos e modificados. Por esses motivos, os programadores logo passaram a usar nomes para as operações e dados, como mostrado na seção seguinte.
As instruções mostradas em linguagem de máquina na seção anterior como a seguir. Supomos que x é o nome de um lugar ou posição da área de dados, correspondente ao endereço BBEh, e que L é um lugar ou posição da área de instruções do programa, correspondente ao endereço 0x00e5.
| MOV R1, #5 |
| MOV R2, x |
| ADD R1, R2 |
| JGE L |
Um programa escrito nessa forma era então manualmente traduzido para linguagem de máquina, e depois carregado na memória do computador para ser executado.
O passo seguinte foi transferir para o próprio computador essa tarefa de “montar” o programa em linguagem de máquina, desenvolvendo um programa para realizar essa tarefa. Esse programa é chamado de montador (em inglês, assembler), e a notação simbólica dos programas que ele traduz é chamada de linguagem de montagem (em inglês, assembly language).
Desenvolver programas em linguagem de montagem continuava sendo, entretanto, uma tarefa difícil e sujeita a grande quantidade de erros, que geravam programas difíceis de serem estendidos e modificados. A razão é que as instruções dessa linguagem, exatamente as mesmas da linguagem de máquina, têm pouca relação com as abstrações usualmente empregadas pelo programador na construção de algoritmos para a solução de problemas.
Para facilitar a tarefa de programação, e torná-la mais produtiva, foram então desenvolvidas novas linguagens de programação. Essas novas linguagens foram chamadas linguagens de alto nível, por oferecer um conjunto muito mais rico de operações e construções sintáticas adequadas para expressar, de maneira mais natural, algoritmos usados na solução de problemas. Linguagens de máquina e linguagens de montagem são chamadas, em contraposição, linguagens de baixo nível.
Para que um programa escrito em uma linguagem de alto nível possa ser executado pelo computador, ele precisa ser primeiro traduzido para um programa equivalente em linguagem de máquina. Esse processo de tradução é chamado de compilação; o programa que faz essa tradução é chamado de compilador. Um compilador é, portanto, simplesmente um programa tradutor, de programas escritos em uma determinada linguagem, chamada de linguagem fonte, para programas em outra linguagem, chamada de linguagem objeto. Os programas fornecidos como entrada e obtidos como saída de um compilador são também comumente chamados, respectivamente, de programa fonte (ou código fonte) e programa objeto (ou código objeto).
Um compilador analisa o texto de um programa fonte para determinar se ele está sintaticamente correto, isto é, em conformidade com as regras da gramática da linguagem e, em caso afirmativo, gera um código objeto equivalente. Caso o programa fonte contenha algum erro, o compilador então emite mensagens que auxiliam o programador na identificação e correção dos erros existentes.
Outro processo para execução de um programa em linguagem de alto nível, em vez da compilação desse programa seguida pela execução do código objeto correspondente, é a interpretação do programa fonte diretamente. Um interpretador é, como o nome indica, um programa que interpreta diretamente as frases do programa fonte, isto é, simula a execução dos comandos desse programa sobre um conjunto de dados, também fornecidos como entrada para o interpretador. A interpretação de programas escritos em uma determinada linguagem define uma “máquina virtual”, na qual é realizada a execução de instruções dessa linguagem.
A interpretação de um programa em linguagem de alto nível pode ser centenas de vezes mais lenta do que a execução do código objeto gerado para esse programa pelo compilador. A razão disso é que o processo de interpretação envolve simultaneamente a análise e simulação da execução de cada instrução do programa, ao passo que essa análise é feita previamente, durante a compilação, no segundo caso. Apesar de ser menos eficiente, o uso de interpretadores muitas vezes é útil, principalmente devido ao fato de que, em geral, é mais fácil desenvolver um interpretador do que um compilador para uma determinada linguagem.
Esse aspecto foi explorado pelos projetistas de linguagens tais como Java, no desenvolvimento de sistemas (ou ambientes) para programação e execução de programas nessa linguagem: esses ambientes são baseados em uma combinação dos processos de compilação e interpretação. Um ambiente de programação Java é constituído de um compilador Java, que gera um código de mais baixo nível, chamado de bytecodes, que é então interpretado. Um interpretador de bytecodes interpreta instruções da chamada “Máquina Virtual Java” (Em inglês JVM – Java Virtual Machine) Esse esquema usado no ambiente de programação Java não apenas contribuiu para facilitar a implementação da linguagem em grande número de computadores diferentes, mas constitui uma característica essencial no desenvolvimento de aplicações voltadas para a Internet, pois possibilita que um programa compilado em um determinado computador possa ser transferido através da rede e executado em qualquer outro computador que disponha de um interpretador de bytecodes. Outras linguagens interpretadas muito conhecidas são Phyton e Lua. Lua é uma linguagem de programação projetada na PUC-Rio e desenvolvida principalmente no Brasil, formando atualmente parte do Ginga, o padrão brasileiro de televisão digital.
Além de compiladores e interpretadores, um ambiente de programação de uma determinada linguagem de alto nível oferece, em geral, um conjunto de bibliotecas de componentes ou módulos de programas, usados comumente no desenvolvimento de programas para diversas aplicações. Além disso, ambientes de programação incluem outras ferramentas para uso no desenvolvimento de programas, como editores de texto e depuradores de programas.
Um editor é um programa usado para criar um arquivo de dados e modificar ou armazenar dados nesse arquivo. O tipo mais simples de editor é um editor de texto, que permite “editar” (i.e. criar ou modificar) qualquer documento textual (um “texto” significando uma seqüência de caracteres, separados linha por linha). Alguns editores usam caracteres especiais, chamados de caracteres de controle, para facilitar a visualização do texto editado, por exemplo colocando em destaque (em negrito ou com uma cor diferente) palavras-chave da linguagem.
Um depurador é um programa que oferece funções específicas para acompanhamento da execução de um programa, com o objetivo de auxiliar o programador na detecção e identificação da origem de erros que possam existir em um programa.
Em um ambiente de programação convencional, editores, compiladores, interpretadores e depuradores são programas independentes. Em um ambiente integrado de programação, ao contrário, as tarefas de edição, compilação, interpretação e depuração são oferecidas como opções disponíveis em um mesmo programa.
A execução de programas em um computador é iniciada e controlada por um programa denominado sistema operacional. O sistema operacional controla a operação em conjunto dos diversos componentes do computador — processador, memória e dispositivos de entrada e saída — assim como a execução simultânea de diversos programas pelo computador. A execução do núcleo do sistema operacional é iniciada no momento em que o computador é ligado, quando esse núcleo é transferido do disco para a memória do computador, permanecendo residente na memória enquanto o computador estiver ligado. O núcleo do sistema operacional provê uma interface adequada entre a máquina e os demais programas do sistema operacional que, por sua vez, oferecem uma interface adequada entre os diversos componentes do computador e os usuários e seus programas, em um ambiente de programação.
A notação hindu-arábica, que usamos para escrever números em nosso sistema de numeração decimal, teria sido originada na Índia, no terceiro século a.C., sendo mais tarde levada para Bagdá, no oitavo século d.C. É interessante observar que o símbolo que representa o número zero só apareceu em um estágio posterior do desenvolvimento dessa notação, no século nove d.C. O nome notação arábica, mais comumente usado, se deve ao fato de que essa notação foi divulgada pela primeira vez por um matemático árabe, chamado al-Khuarizmi — daí o nome algarismo, dado aos símbolos que usamos atualmente para a representação de números no nosso sistema de numeração.
A característica fundamental da notação hindu-arábica, que torna mais fácil representar números grandes e realizar operações sobre números, é o fato de ela ser uma notação posicional. No nosso sistema de numeração, de base 10, a posição de cada algarismo determina as potências de 10 pelas quais devem ser multiplicados os números denotados por esses algarismos, para obter o número representado.
Por exemplo:
| 496 = 4× 102 + 9 × 101 + 6× 100 |
Essa notação pode ser usada, de modo geral, para representação de números em um sistema de numeração de base b qualquer, onde b é um número inteiro positivo, com base no fato de que qualquer número inteiro não-negativo p pode ser univocamente representado na forma
| p= |
| di× bi |
onde cada di, para i=0,…,n, é um símbolo que representa um número de 0 a b−1.
No sistema de numeração binário (de base 2), o numeral 1011, por exemplo, representa o número decimal 11, conforme se mostra a seguir (um subscrito é usado para indicar a base do sistema de numeração em cada caso):
| 10112 = 1× 23 + 0 × 22 + 1× 21 + 1× 20 = 1110 |
Exercício: Converta o número 1101012 para a sua representação no sistema decimal.
Para converter um número p, escrito na base 10, para a sua representação na base 2, basta notar que, se p=∑i=0n di × 2i, onde di=0 ou di=1, para i=0,…,n, e dn≠0, temos que 2n+1 < p ≤ 2n. Portanto, efetuando n divisões sucessivas de p por 2, obtemos:
|
uma vez que teremos qn=0.
O processo de conversão de um número da sua representação decimal para a sua representação binária, pode ser feito, portanto, como mostra a Figura 1.2, onde se ilustra essa conversão para o número decimal 13.
Figura 1.2: Conversão de representação de número, de decimal para binária
Exercício: converta o número 29510 para a sua representação na base binária.
Os componentes básicos dos circuitos eletrônicos de um computador moderno são chamados de portas lógicas. Uma porta lógica é simplesmente um circuito eletrônico que produz um sinal de saída, representado como 1 ou 0 e interpretado como “verdadeiro” (V) ou “falso” (F), respectivamente, que é o resultado de uma operação lógica sobre os seus sinais de entrada.
Essas operações lógicas — “não”, “ê”, “ou”, “ou exclusivo”, representadas pelos símbolos (ou conectivos lógicos) ¬, ∧, ∨, ⊕, respectivamente — são definidas na Tabela 1.1.
Tabela 1.1: As operações lógicas “não”, “ê”, “ou” e “ou exclusivo”
Operação Resultado “não” ¬ V F ¬ F V
Operação Resultado (“ê”) (“ou”) (“ou exclusivo”) op = ∧ op = ∨ op = ⊕ V op V V V F V op F F V V F op V F V V F op F F F F
O conjunto constituído dos valores “verdadeiro” e “falso” é chamado de conjunto Booleano, em homenagem ao matemático George Boole (1815-1864), um dos pioneiros na formalização da lógica matemática. Analogamente, os valores desse conjunto são chamados de valores booleanos e as operações lógicas definidas sobre esse conjunto são chamadas de operações booleanas, ou operações da Lógica Booleana (ou Lógica Proposicional).
A operação lógica “ê” tem resultado verdadeiro se ambos os operandos são verdadeiros, e falso em caso contrário. A operação lógica “ou” tem resultado falso se ambos os operando são falsos, e verdadeiro em caso contrário. A operação lógica “ou exclusivo” tem resultado verdadeiro se um dos operandos, mas não ambos, é verdadeiro, e falso caso contrário.
Para entender como portas lógicas podem ser usadas para implementar a soma de números inteiros positivos em um computador, considere primeiramente a soma de dois números n e m, representados na base binária, cada qual com apenas 1 bit, ilustrada a seguir:
|
Ao comparar a tabela acima com as operações lógicas definidas na Tabela 1.1, é fácil perceber que a operação lógica “ou exclusivo” fornece o bit r do numeral que representa o resultado da soma n+m: o bit r é igual a 1 se n ou m for igual a 1, mas não ambos, e é igual a 0, caso contrário. O bit “vai um” desse numeral é obtido pela operação lógica “ê”: o bit “vai um” é igual a 1 quando n e m são iguais a 1, e é igual a 0 em caso contrário.
O resultado da soma n+m pode ser, portanto, representado pelo par (n ∧ m, n ⊕ m), em que o primeiro componente é o bit “vai um” e o segundo é o bit r do resultado. Note que m ⊕ n = (m ∨ n) ∧ ¬ (m ∧ n).
Com base nessas observações, fica fácil construir um circuito para somar dois números binários n e m, cada qual representado com apenas 1 bit. Esse circuito, chamado de meio-somador, é apresentado na Figura 1.3. Símbolos usuais são empregados, nessa figura, para representar as portas lógicas que implementam as operações “ê”, “ou” e “não”.
Figura 1.3: Circuito do meio-somador
O meio-somador pode ser usado para construir um circuito que implementa a soma de três números binários n, m e p, cada qual representado com apenas 1 bit, usando o fato de que a operação de adição é associativa: n+m+p = (n+m)+p. Sendo n+m = (v1, r1) e r1 + p = (v2, r), temos que n+m+p = (v1 ∨ v2, r), uma vez que v1 e v2 não podem ser ambos iguais a 1. O circuito lógico que implementa a soma n+m+p, chamado de somador completo, pode ser construído como mostra a Figura 1.4.
Figura 1.4: Circuito do somador completo
Podemos agora facilmente construir o chamado somador paralelo, para somar números inteiros, representados no sistema de numeração binário, com qualquer número fixo de bits.
A Figura 1.5 ilustra um circuito somador paralelo para somar números binários n e m, cada qual representado com 3 bits, ABC e DEF, respectivamente.
Figura 1.5: Circuito do somador paralelo
Para maior facilidade de armazenamento e de operação, todo número é representado, em um computador, por uma seqüência de bits de tamanho fixo. No caso de números inteiros, esse tamanho é igual ao número de bits que podem ser armazenados na palavra do computador. Em grande parte dos computadores modernos, esse tamanho é de 32 bits ou, em computadores ainda mais modernos, de 64 bits.
Para representar tanto números inteiros não-negativos quanto negativos, um determinado bit dessa seqüência poderia ser usado para indicar o sinal do número — essa abordagem é chamada de sinal-magnitude.
A abordagem de sinal-magnitude não é muito adequada, pois existem nesse caso duas possíveis representações para o zero e as operações de somar números não é tão simples quanto no caso da representação em complemento de dois, usada em todos os computadores modernos.
A característica fundamental dessa representação é a de que a operação de somar 1 ao maior inteiro positivo fornece o menor inteiro negativo. Desse modo existe apenas uma representação para o zero e pode-se realizar operações aritméticas de modo bastante simples.
Ilustramos, na Tabela 1.2, a representação de números na notação de complemento de 2 em um computador com uma palavra de apenas 4 bits. Note que existem 2n combinações distintas em uma palavra de n bits, e portanto é possível representar 2n números inteiros, que na representação de complemento de dois compreendem os inteiros na faixa de −2(n−1) a 2(n−1)−1.
O complemento de 2 de um número inteiro positivo p, 0< p≤ 2n−1, com relação a n bits, denotado por c2n(p), é definido como sendo a representação na base binária, com n bits, do número positivo 2n − p. Na notação de complemento de 2, um número inteiro p ≥ 0 é representado na base binária, com n bits, da maneira usual, e um número inteiro p<0 é representado pelo complemento de 2 do valor absoluto de p, c2n(|p|).
Tabela 1.2: Representação de inteiros em 4 bits
0 0000 -8 1000 1 0001 -1 1111 2 0010 -2 1110 3 0011 -3 1101 4 0100 -4 1100 5 0101 -5 1011 6 0110 -6 1010 7 0111 -7 1001
Dado um número inteiro positivo p, uma maneira eficiente para calcular c2n(p), a partir da representação de p na base binária, pode ser obtida pela observação de que c2n(p) = 2n − p = (2n − 1) − p + 1. Como a representação de 2n−1 na base binária consiste de uma seqüência de n 1s, é fácil ver que, para obter o resultado da subtração (2n − 1)−p, ou seja, c2n(p)−1, também chamado de complemento de 1 de p, basta tomar a representação de p na base binária e trocar, nessa representação, os 1s por 0s e vice-versa. Para obter c2n(p), precisamos então apenas somar 1 ao resultado obtido.
Por exemplo:
|
Exercício: Como seriam representados os números 17 e −17, em um computador com palavra de tamanho igual a 8 bits?
Para obter a representação usual de um número inteiro p na base binária, dada a sua representação na notação de complemento de 2, basta observar que 2n − (2n − p) = p. Portanto, dado cn2(p), a representação de p na base binária pode ser obtida calculando o complemento de 2 de c2n(p), ou seja, c2n(c2n(p)). Por exemplo: de c24(p) = 11112 obtemos p=c24(11112)=00012.
Exercício: Determine a representação na base decimal do número p tal que c24(p)=10102.
Exercício: Determine a representação na base decimal dos números representados por 01100001 e 10011111, em um computador com palavra de tamanho igual a 8 bits.
Você provavelmente terá observado que o bit mais à esquerda da representação de um número inteiro na notação de complemento de 2 é igual a 1, se o número for negativo, e igual a 0, caso contrário. Esse bit pode ser, portanto, interpretado como o sinal do número.
Usando essa representação, a adição de dois números inteiros n e m pode ser feita da maneira usual, sendo descartado o bit “vai um” obtido mais à esquerda. Por exemplo:
| |||||||||||||||||||||||
Ou seja, 6 + (−7) = −1 e (−2) + (−3) = (−5).
A demonstração de que esse procedimento fornece o resultado correto para a operação de adição foge um pouco do escopo deste livro.
| (a) 19 | (b) 458 |
| (a) 11102 | (b) 1101102 |
| (a) 1011 + 101 | (b) 10100 − 1101 |
| (a) -23 | (b) -108 |
| (a) 11010011 | (b) 11110000 |
| (a) 57 + (−118) | (b) (−15) + (−46) |
Os primeiros estudos em ciência da computação, realizados por volta de 1935, estabeleceram os fundamentos teóricos da área, lançando as bases para a construção dos primeiros computadores. Como resultado desses estudos, foi estabelecida uma caracterização formal para a noção intuitiva de algoritmo, e concluiu-se também existem problemas chamados indecidíveis, cuja solução não pode ser obtida por meio de nenhum programa de computador. Ao leitor interessado em saber mais sobre esse assunto, recomendamosa leitura de [25]. Uma discussão interessante sobre a influência dos recentes resultados da teoria da computação no desenvolvimento tecnológico e científico alcançados no século 20 é apresentada em [13] e [23].
Para um bom entendimento sobre os fundamentos teóricos da computação, é necessário algum conhecimento de matemática discreta, que abrange temas como lógica matemática, teoria de conjuntos, relações e funções, indução e recursão. Dois livros excelentes, que abordam esses temas de maneira introdutória, são [6] e [30].
O funcionamento e organização de computadores, descritos brevemente neste capítulo, é discutido detalhadamente em diversos livros específicos sobre o assunto, dentre os quais recomendamos [31, 2, 7].
