Algebra Booleana
De ccppbrasil.org
Tabela de conteúdo |
Introdução
A algebra booleana trata de expressões lógicas. George Boole inventou esta algebra para analisar expressões lógicas envolvendo conjuntos (que ele chamava de classes), porém atualmente a usamos principalmente com variáveis que podem assumir um dentre dois valores: verdadeiro ou falso, 0 ou 1, Sim ou Não, etc.
A algebra booleana pode ser facilmente expressa através de circuitos elétricos e eletrônicos e é a base do projeto dos computadores digitais.
Na programação, um conceito essencial é o desvio (ou tomada de decisão) que consiste em mudar a ordem de execução conforme uma expressão lógica.
Neste artigo veremos uma descrição sucinta da algebra booleana e como ela é implementada no C e no C++.
Algebra Booleana
Conforme mencionado, a algebra booleana envolve variáveis que podem assumir somente dois valores. Nesta descrição vamos chamar estes valores de 0 e 1, porém lembre-se que eles podem significar qualquer par de condições que sejam exclusivas (isto é, uma variável não pode ser 0 e 1 simultaneamente) e complementares (isto é, se não for 0 é 1 e vice-versa).
Uma forma de representar as operações da algebra booleana é através das tabelas verdade, que mostram os resultados para todas as combinações de entrada.
Uma primeira operação lógica é a negação (ou complemento), que vamos representar por !
A !A 0 1 1 0
Uma segunda operação é o E (ou AND) que vamos representar por &&:
A B A&&B 0 0 0 0 1 0 1 0 0 1 1 1
Ou seja, o E resulta em 1 somente se os dois operandos forem 1.
Outra operação é o OU (ou OR),representado abaixo por ||
A B A||B 0 0 0 0 1 1 1 0 1 1 1 1
O OU resulta em 1 se pelo menos um dos operandos for 1.
Por último vamos considerar o OU EXCLUSIVO (ou XOR), representado abaixo por ^:
A B A^B 0 0 0 0 1 1 1 0 1 1 1 0
O XOR resulta 1 se somente um dos operados for 1. O XOR é equivalente a uma combinação de E e OU:
A^B = (A||B) && !(A&&B)
Nos circuitos eletrônicos é comum encontrarmos outros tipos de operações:
A NAND B = !(A && B) A NOR B = !(A || B)
Da mesma forma que na aritmética e algebra comuns, as operações booleanas apresentam uma série de propriedades úteis:
A && 1 = A (elemento neutro) A && 0 = 0 A && A = A A && B = B && A (comutativa) (A && B) && C = A && (B && C) (associativa) A || 0 = A A || 1 = 1 A || A = A A || B = B || A (A || B) || C = A || (B || C) A ^ 0 = A A ^ 1 = !A A ^ A = 0 A ^ B = B ^ A (A ^ B) ^ C = A ^ (B ^ C) A && (B || C) = (A && B) || (A && C) A || (B && C) = (A || B) && (A || C) !(A && B) = (!A) || (!B) !(A || B) = (!A) && (!C)
Algebra Booleana em C
Variáveis e expressões lógicas
Ao contrário de outras linguagens, o C não possui um tipo de dados lógico, que aceite somente valores verdadeiro e falso. O C utiliza para armazenar valores lógicos os tipos inteiros. Uma expressão em C engloba tanto expressões lógicas como aritméticas. Tudo isto é possível através de duas convenções básicas:
- ao testar o valor lógico do resultado de uma expressão, o resultado é considerado verdadeiro se for diferente de zero e falso se for igual a zero
- ao atribuir a uma variável o resultado de uma expressão lógica, este resultado será 1 se a expressão for verdadeira e 0 se a expressão for falsa.
Convencionalmente, mas não obrigatoriamente, as constantes TRUE e FALSE são definidas como:
#define FALSE 0 #define TRUE 1
Sintomaticamente, estes defines não são encontrados nos includes padrão do C (porém estão nos includes da API do Windows).
Um resultado lógico é obtido através dos operadores de comparação e dos operadores lógicos:
comparação
== igual
!= diferente
> maior
< menor
>= maior ou igual
<= menor ou igual
lógico
! negação
&& e
|| ou
Uma característica importante do C é que o cálculo de expressões com && e || é feito da esquerda para a direita até que o resultado final seja determinado. Em outras palavras, o cálculo é encerrado quando o primeiro termos de && resulta em falso ou o primeiro termo de || resulta em verdadeiro.
Em outras linguagens o compilador tem a liberdade de calcular a expressão na ordem que desejar, podendo ou não executar todos os termos. O fato do C estipular claramente a ordem de execução, permite escrever de forma segura trechos como o abaixo:
char s[10]; int i; for (i = 0; (i < sizeof(s)) && (s[i] != 0); i++) ;
A ordem de cálculo do && garante que nunca será calculado s[i] com um índice inválido. A ordem também é importante quando a expressão envolve funções e/ou operações com efeitos colaterais. Citando um exemplo do K&R:
void getline (char *s, int lim)
{
int c, i;
for (i = 0; i < (lim-1) && (c = getchar()) != '\n') && (c != EOF); i++)
s[i] = c;
s[i] = 0;
}
Note que getchar só será chamado se i < (lim-1) for verdade (ou seja, existe espaço em s para guardar o caracter lido).
Manipulação de Bits
Além do uso da algebra booleana em expressões lógicas, o C possui operadores para fazer operações lógicas sobre os bits de uma expressão inteira. Isto expõe ao programador C operações bastante comuns da linguagem de máquina. Os operadores binários são:
& e | ou ^ ou exclusivo ~ negação << deslocamento (shift) para a esquerda >> deslocamento para a direita
Ao contrário dos operadores lógicos, os operadores binários não retornam um valor 0 ou 1. Os operadores binários operam em paralelo sobre todos os bits do valor. Alguns exemplos simples, supondo que char seja armazenado em 8 bits e int em 32 bits:
unsigned char byte; unsigned int uint32; byte = ~0x55; // byte fica com 0xAA uint32 = ~0x55; // uint32 fica com 0xFFFFFFAA byte = 0x33 & 0x11; // byte fica com 0x11
A expressão a << b resulta em a deslocado para a esquerda b bits, com b zeros acrescentados à direita (em outras palavras, multiplica por 2 elevado a b). Por exemplo:
1 << 1 resulta em 2 1 << 3 resulta em 8
A expressão a >> b resulta, com a sendo unsigned, resulta em a deslocado para a direita b bits, com b zeros acrescentados à esquerda (em outras palavras, divide por 2 elevado a b). Se a for um valor com sinal, os bits acrescentados à esquerda podem variar de compilador a compilador e devem, portanto, ser considerados indefinidos.
A linguagem C permite declarar dentro de uma estrutura campos inteiros (int, unsigned int ou signed int) com um determinado número de bits (bit fields). O compilador é responsável por associar estes campos aos bits de armazenamento, o único controle que o programador tem é que um campo de "zero bits" força o campo seguinte a iniciar na próxima unidade de alocação (que também é dependente da implementação). Os bit fields podem ser úteis para economizar memória, porém criam problemas de portabilidade e compatibilidade, principalmente quando podem ser acessados por código compilado com compiladores diferentes.
Um exemplo de uso de bit fiels:
struct
{
int baudrate; // um inteiro normal
int stopbits:1; // stopbits é um inteiro de 1 bit (0 ou 1)
int databits:4; // databits é um inteiro de 4 bits (0 a 15)
int paridade:2; // paridade é um inteiro de 2 bits (0 a 3)
int fXonXoff:1; // fXonXoff é um inteiro de 1 bit (0 ou 1)
} cfgSerial;
cfgSerial.databits = 7; // o compilador coloca o valor nos bits corretos
cfgSerial.fXonXof = 1; // idem
if (cfgSerial.paridade == 2) // o compilador testa os bits da paridade
{
...
}
Costumes e Práticas - Expressões Lógicas
Tradicionalmente, variáveis que armazenam valores lógicos e funções que retornam valores lógicos são declaradas com o tipo int. Em situações em que a memória é reduzida (vide C Embarcado), pode-se usar char no seu lugar.
A forma mais comum de usar variáveis lógicas é a seguinte:
int fMaior;
fMaior = a > b;
...
if (fMaior)
{
...
}
O fato de que fMaior irá conter 0 ou 1, fica totalmente implicito neste caso.
Ocasionalmente encontra-se o teste explicito de uma variável lógica com o valor 1:
#define TRUE 1
int fMaior;
fMaior = a > b;
...
if (fMaior == TRUE)
{
...
}
É também comum suprimir a comparação de um valor inteiro (não lógico) com zero em uma expressão lógica:
int nTam;
nTam = strlen (s);
...
if (nTam) // estamos testando nTam != 0, não nTam == TRUE
{
...
}
Uma variação não tão legível deste exemplo é
int nTam;
nTam = strlen (s);
...
if (!nTam) // estamos testando nTam == 0
{
...
}
Pessoalmente, acho mais claro e direto escrever if (fMaior) e if (nTam != 0), mas não existe nada de errado nas outras maneiras.
O fato de expressões lógicas e aritméticas serem praticamente equivalentes abre as portas para um série de truques de qualidade duvidosa:
int a, b, c;
a = strlen(s1);
b = strlen (s2);
if (!(a + b)) // equivale a (a+b)== 0 ou (a==0)&&(b==0)
{
...
}
c = 10 + (a > b)*3; // equivale a c = (a > b) ? 13 : 10;
Costumes e Práticas - Manipulação de Bits
O uso mais comum da manipulação de bits é para armazenar em uma única variável vários flags. Isto reduz o consumo de memória e a passagem de parâmetros. Um exemplo típico:
#define FL_A 0x01
#define FL_B 0x02
#define FL_C 0x04
int flags;
// Inicia flags com apenas o flag C ligado
flags = FL_C;
// Liga os flags A e B sem afetar os demais
flags |= (FL_A | FL_B);
// Testa se o flag B está ligado
if (flags & FL_B)
{
...
}
// Desliga o flag C sem afetar os demais
flags &= ~FL_C;
// Inverte o estado do flag A, sem afetar os demais
flags ^= FL_A;
O exclusivo e o deslocamente aparecem também no cálculo de CRCs (cyclic redundance codes), usados como um controle para confererir se uma mensagem foi recebida sem erros. Originalmente, os CRCs eram implementados em hardware, um circuto recebia um a um os bits transmitidos ou recebidos e os deslocava para um registrador de n bits e os combinava através de ou exclusivo. O trecho abixo mostra uma forma (ineficiente) de calcular o CRC-16 padrão CCITT:
unsigned crc16 (unsigned char *p, int n)
{
int iByte, iBit, flag;
unsigned crc;
unsigned char b;
crc = 0;
for (iByte = 0; iByte < n; iByte++)
{
b = p[iByte];
for (iBit = 0; iBit < 8; iBit++)
{
flag = crc & 0x8000;
crc <<= 1;
if (b & 0x80)
crc |= 1;
if (flag)
crc ^= 0x1021;
b <<= 1;
}
}
return crc & 0xFFFF;
}
Não podemos encerrar sem mecionar o clássico truque de usar ou exclusivo para trocar o conteúdo de duas variáveis sem usar uma variável auxiliar
a ^= b; b ^= a; // b = b^(a^b) = b^(b^a) = (b^b)^a = 0^a = a a ^= b; // a = a^(a^b) = (a^a)^b = 0^b = b
Algebra Booleana em C++
O C++ acrescenta um tipo bool. Uma variável do tipo bool pode ter um dentre dois valores: true ou false. Por compatibilidade com o C, existem as seguintes regras:
- os valores lógicos false e true são convertidos implicitamente para os valores numéricos 0 e 1
- valores numéricos são convertidos implicitamente para false (se forem zero) ou true (se forem diferentes de zero)
- nas expressões lógicas e aritméticas, os valores lógicos são convertidos para valores inteiros, as operações lógicas e aritméticas da expressão são efetuadas sobre estes valores. Como no C, as expressões lógicas retornam um valor inteiro.
Desta forma, o uso da algebra booleana em C++ é muito semelhante ao uso no C. O tipo bool facilita documentar quais as variáveis armazenam exclusivamente valores lógicos.
Referências
- Charles Petzold, Code
- Kernighan&Ritchie, The C Programming Language, second edition
- Bjarne Stroustrup, The C++ Programming Language, 3rd edition
- Tery Ritter, The Great CRC Mystery, Dr Dobb's Journal, fev 86
- Donald Krantz, Christensen Protocol in C, Dr Dobb's Journal, jun 85
--Dq 11:20, 25 Abril 2006 (CDT)
