Operador OR binário

O operador “ou” binário, corresponde à operação de disjunção. É ainda designado por “OR” binário, sendo representado na linguagem C através do símbolo da barra vertical |. A tabela de verdade do operador OR binário (Tabela 5) mostra que sempre que um dos operandos é o bit 1, o resultado final é o bit 1, independentemente do valor do outro operando. Por sua vez, o bit 0 é o elemento neutro do operador OR binário, dado que o resultado de um OR binário com um dos operandos a bit 0 é determinado pelo valor do outro operando: 0 se o outro operando for bit a 0, e 1 se o outro operando for bit a 1.

Um dos usos do operador OR binário é a ativação de um bit, isto é, colocar a 1 um determinado bit. Por exemplo, o resultado da operação OR binário com o operando 0011, terá sempre os dois bits menos significativos à 1, independentemente do valor do outro operando. De facto, conforme anteriormente observado, sempre que um determinado bit dos operandos do operador OR binário é 1, o resultado do bit correspondente é também ele 1. O código or_binario.c (Listagem 10) exemplifica o uso do de 0x003, ou seja 0000.0000.0011b como operando no operador OR binário, originando um resultado cujos dois bits menos significativos têm o valor 1 (Listagem 11).

/* Exemplo: or_binario.c */
#include <stdio.h>

int main(void){
 int a = 0x003;/* 0000.0000.0011b, 3 base10 */
 int b = 0x120;/* 0001.0010.0000b, 288 base10 */
 int c;
 c = a | b; /* or binario */
 /* 0000.0000.0011 | 0001.0010.0000 
 => 0001.0010.0011 */
 printf("c = %d | %d => %d\n", a, b, c);
 return 0;
}

À semelhança do anteriormente visto para o operador AND, existe também na linguagem C um operador OR lógico, representado através de dupla barra vertical, isto é, ||. Com exceção da tabela de verdade (Tabela 6) que obviamente difere da tabela do AND lógico, tudo o anteriormente mencionado para o operador AND lógico se mantém.

Operador ou exclusivo (xor)

O operador ou exclusivo, ou xor na designação anglo-saxónica (contração de eXclusive OR) é também conhecido por disjunção exclusiva. Na linguagem C, o operador XOR é representado pelo símbolo ^. Conforme mostra a tabela de verdade (Tabela 7), a operação de XOR resulta no bit 1 se os dois operandos corresponderem a bits diferentes (i.e., um dos operandos é o bit a 1 e o outro o bit a 0). Caso ambos os operandos representem o mesmo bit, então o resultado da operação de XOR é o bit a 0.

Uma das aplicações do operador XOR binário é o cálculo de paridade de um determinado conjunto de bits. A paridade par de uma sequência de bits diz-se par se o número de bits a 1 na sequência é par, e ímpar se o número de bits a 1 na sequência é ímpar. A Listagem 12 apresenta código em linguagem C que calcula a sequência de paridade de uma sequência de sete inteiros.

/*
 * Exemplo: xor_paridade.c
 * Patricio R. Domingues
 */
#include <stdio.h>

int main(void){
 /* Vetor de 7 inteiros sobre os 
 quais é calculada a sequencia de paridade */
 int i;
 int paridade; /* Sequência de paridade */
 int vetor_entrada[7];
 vetor_entrada[0] = 0x12; /* 0001.0010 */
 vetor_entrada[1] = 0x02; /* 0000.0010 */
 vetor_entrada[2] = 0x22; /* 0010.0010 */
 vetor_entrada[3] = 0x00; /* 0000.0000 */
 vetor_entrada[4] = 0xA0; /* 1010.0000 */
 vetor_entrada[5] = 0xFA; /* 1111.1010 */
 vetor_entrada[6] = 0x4D; /* 0100.1101 */
 /* Sequencia de paridade esperada: 0010.0101 */
 paridade = vetor_entrada[0];
 for(i=1; i<7; i++){
 paridade = paridade ^ vetor_entrada[i];
 }
 printf("paridade=0x%x (hex)\n", paridade);
 return 0;
}

No exemplo apresentado, cada inteiro é representado por dois símbolos hexadecimais, considerando-se assim apenas 8 bits por inteiro (independentemente de cada inteiro ter 32 bits – os bits mais significativos para além do oitavo bit estão a zero). O cálculo da sequência de paridade resume-se a aplicar a operação de XOR de forma iterativa entre os sete elementos da sequência de entrada, usando-se para o efeito a variável paridade para guardar a sequência de paridade. Note-se que a sequência de paridade corresponde à sequência de bits que é necessário acrescentar à sequência de entrada para obter paridade par.

É importante observar que no exemplo apresentado se está a considerar as sequências de bits que ocorrem na vertical, calculando-se o respetivo bit de paridade. Por exemplo, uma das sequências é formada pelo bit mais significativo (relembre-se, o bit mais à esquerda) dos sete valores inteiros, corresponde à sequência 0000.110, sendo o bit de paridade o bit 0 por forma que a sequência de oito bits (sete mais o bit de paridade) tenha paridade par, isto é, um número par de bits a 1. A sequência de paridade é pois 0010.0101, ou equivalentemente, 0x25 em hexadecimal. A Tabela 8 mostra os sete conjuntos de bits e a respetiva sequência de paridade.

Embora a linguagem C não disponibilize o operador lógico XOR, a operação XOR entre valores lógicos pode ser obtida através do recurso aos operadores AND, OR e NOT, conforme mostrado na Equação 1.

Uma aplicação comum do operador XOR, especialmente em assembler, é o de zerar o valor de uma variável. Para o efeito, efetua-se o XOR da variável com ela própria (a = a xor a) levando a que o resultado final seja zero, pois a xor a é garantidamente zero.

Operador deslocamento para a esquerda

Como o nome sugere, os operadores de deslocamento efetuam o deslocamento de bits. Na linguagem C, o operador deslocamento para a esquerda tem a seguinte sintaxe: valor << n. O operador de deslocamento à esquerda efetua uma translação em n posições dos bits para a esquerda do valor especificado. A Figura 1 ilustra uma operação de deslocamento para a esquerda em um bit do valor 0001.0010, resultando no valor 0010.0100. Note-se que devido ao deslocamento à esquerda em 1 bit, o anterior bit mais significativo (bit mais à esquerda) é perdido, sendo acrescentado um bit a 0 para a posição do bit menos significativo (bit mais à direita, representado a azul). Caso o deslocamento fosse de n bits para a esquerda, perder-se-iam os n bits mais significativos, sendo ainda acrescentados n bits a 0 como bits menos significativos.

Quando efetuada sobre a representação binária de um número inteiro, a operação deslocamento para a esquerda em n bits produz um valor que corresponde à multiplicação por 2ⁿ do valor inteiro original. Por exemplo, na Figura 1, o deslocamento em um bit para a esquerda do valor original 0001.0010 que corresponde ao inteiro 18 em base decimal, é transformado no valor 0010.0100 que corresponde ao valor 36 em base decimal, isto é, ao dobro do valor original. Esta propriedade do operador deslocamento para a esquerda é frequentemente empregue, especialmente em linguagens assembler, para efetuar multiplicações de valores inteiros por 2ⁿ, pois é bastante mais rápida do que o algoritmo de multiplicação entre dois números inteiros.

A Listagem 13 mostra um exemplo de uso do operador deslocamento para a esquerda. Nesse exemplo, é aplicado a rotação à esquerda ao valor inteiro 1, usando-se um operando de deslocamento (variável i) que incrementa em cada iteração do ciclo for. Deste modo, na 1ª iteração do ciclo (i=0), o valor inteiro 1 não é deslocado, não sendo pois alterado. Na iteração seguinte (i=1) o valor 1 é deslocado em 1 bit para a esquerda, passando de 0…001 para 0…010, correspondendo ao valor inteiro 2. Na iteração seguinte (i=2), o valor inteiro 1 é deslocado para a esquerda em dois bits, resultando no valor 0…100, correspondendo ao valor 4. A Listagem 14 apresenta a saída gerada pela execução do programa. Facilmente se depreende que o código da Listagem 13 gera as sucessivas potências do número inteiro 2 (1, 2, 4, 8, 16, 32, 64, 128,…). Acresce-se ainda que os números inteiros potências de dois são frequentemente empregues como operandos dos operadores AND e OR pelo facto da respetiva representação binária comportar apenas um bit a 1, sendo os restantes 0. É frequente a designação de máscara para caracterizar um valor inteiro cuja representação binária tenha somente um bit a 1 ou, pelo contrário, somente um bit a 0.

/*
 * Exemplo: shift_left.c
 * "Manipulação de bits na linguagem C" 
 * Revista Programar 
 * Patricio R. Domingues
 */
#include <stdio.h>
int main(void){
 unsigned int valor = 1;
 unsigned int valor_shift;
 size_t size_bits=sizeof(valor)*8;
 unsigned int i;
 for(i=0;i<size_bits;i++){
 valor_shift = valor << i;
 printf("[shift (valor << %02u)]%u\n", 
 i, valor_shift);
 }
 return 0;
}

Operador deslocamento para a direita

O operador deslocamento para a direita funciona de forma análoga ao operador de deslocamento para a esquerda, alterando-se somente o sentido do deslocamento. Assim, na operação de deslocamento à direita de n bits, há lugar à deslocação de n bits para a direita. A Figura 2 ilustra uma operação de deslocamento à direita. Na linguagem C, o operador deslocamento para a direita é representado pelos símbolos >>, e à semelhança do operador deslocamento para a esquerda requer dois operandos. Do lado esquerdo do operador fica o operando cujo valor irá ser alvo da operação de deslocamento à direita. Por sua vez, o operando do lado direito indica de quantos bits deve o valor inicial ser deslocado.

valor_deslocado = valor_inicial >> num_bits;

/* shift_right.c
 * Patricio R. Domingues
 * Revista Programar, 2015
 */
int main(void){
 int positive = 998;
 unsigned int sem_sinal = 998;
 int positive_shift_R;
 unsigned int sem_sinal_shift_R;
 int i;
 for(i=0; i < 4; i++){
 positive_shift_R = positive >> i;
 printf("===[i=%d]===\n", i);
 printf("positive_shift_R=%d\n", 
 positive_shift_R);
 sem_sinal_shift_R = sem_sinal >> i;
 printf("sem_sinal_shift_R=%d\n",
 sem_sinal_shift_R);
 }
 return 0;
}

A Listagem 15 exemplifica a operação de deslocamento para a direita em duas variáveis de tipos diferentes. A variável sem_sinal é do tipo unsigned int, isto é, um inteiro sem sinal, ao passo que a variável positive corresponde a um inteiro com sinal (tipo int). Ambas as variáveis são inicializadas com o valor 998, sendo aplicada, sucessivamente, a ambas as variáveis a operação de deslocamento para a direita de 0, 1, 2 e 3 bits de deslocamento. A saída resultante da execução do código é mostrada na Listagem 16. Da análise da listagem depreende-se que a operação de deslocamento de n bits para a direita corresponde à divisão inteira por 2ⁿ do valor inicial. Por exemplo, a operação de deslocamento para a direita em dois bits equivale à divisão inteira por 4 (2²) do valor inicial. É contudo necessário ter em atenção que se trata de uma divisão inteira, perdendo-se a parte não inteira do resultado e que este comportamento, conforme veremos mais adiante, apenas é válido para operandos do tipo unsigned, isto é, sem sinal. Por exemplo, a divisão de 998 por 8 (2³) é 124,75, mas quando se procede ao deslocamento em 3 bits para a direita (998 >> 3), obtém-se o valor inteiro 124. Recomenda-se pois cautela no uso do operador deslocamento à direita para efeitos de divisão por 2ⁿ (Steele, 1977).

Uma outra limitação do operador >> envolve o bit mais à esquerda que deve ser acrescentado pelo operador quando ocorre um deslocamento à direita. Dado que o bit mais à esquerda corresponde ao bit mais significativo, que no caso de um valor inteiro com sinal corresponde ao sinal do número: 0 significa que o número é positivo, -1 significa que o número é negativo, considerando que o sistema está a usar representação em complementos de 2. Assim, a operação deslocamento para a direita não pode simplesmente acrescentar um bit zero em lugar do bit mais significativo, pois tal poderá resultar num valor com sinal diferente do valor inicial. No caso da linguagem C, não está definido qual o bit a ser inserido como bit mais significativo pelo operador deslocamento à direita quando lida com inteiros com sinal. Deste modo, o comportamento fica dependente do compilador empregue. No caso do código da Listagem 17, quando compilada com o GCC numa plataforma Linux verifica-se que o operador deslocamento à direita mantém o sinal da valor inicial conforme ilustram os resultados da Listagem 18.

/* shift_right_signed.c
 * Patricio R. Domingues
 * Revista Programar, 2015
 */
#include <stdio.h>
int main(void){
 int positive = 998;
 int negative = -998;
 int positive_shift, negative_shift;
 int I;
 for(i=0; I < 4; i++){
 printf(“===[shift right %d]===\n”,i);
 positive_shift = positive >> I;
 negative_shift = negative >> I;
 printf(“positive_shift=%d\n”,positive_shift);
 printf(“negative_shift=%d\n”,negative_shift);
 }
 return 0;
}

Concretamente, na plataforma considerada, o operador deslocamento para a direita acrescenta um bit a zero se o valor inicial for não negativo, e um bit a um se o valor inicial for negativo. Importa observar, que para números negativos, e considerando que o operador deslocamento à direita aplica a persistência do bit mais significativo, a operação de deslocamento de n bits à direita já não produz uma divisão por 2ⁿ com truncagem. Por exemplo, a operação -998 >> 2 resulta, conforme mostrado na Listagem 18, no valor -250 e não no valor -249 como seria expectável pelo facto da divisão de -998 por 4 resultar em -249,5. Esta particularidade do operador deslocamento à direita tem causado erros em vários sistemas, nomeadamente compiladores conforme discutido por Steele Jr. já em 1977 (Steele, 1977). De modo a evitar a armadilha do operador de deslocamento para a direita, a linguagem Java disponibiliza o operador deslocamento para a direita sem sinal, representado pelo símbolo >>>. Esse operador preenche sempre a posição do bit mais significativo com um bit a zero.

Casos de usos

Apresentam-se de seguida alguns dos casos de usos mais frequentes de manipulação binária.

Deteção do estado de um bit

A deteção do estado de um bit consiste na determinação do valor de um bit, isto é, determinar se está a zero ou a um. Para o efeito, faz-se uso do operador AND binário, usando como operandos o valor que se pretende analisar e uma máscara binária. A máscara binária é inteiramente composta por bits a zero, exceto para o bit a um na posição do bit cujo valor se pretende detetar.

/*
 * Exemplo: mostra representação em 
 * bits do valor inteiro da variável valor
 * "Manipulação de bits na linguagem C" 
 * Revista Programar 
 * Patricio R. Domingues
 */
#include <stdio.h>
#include <assert.h>

int is_bit_um(int valor, int num_bit){
 int num_bits_int = sizeof(valor) * 8;
 assert( num_bit < num_bits_int );
 int mascara_num_bit = (1 << num_bit);
 return ( valor & mascara_num_bit );
}
int main(void){
 int hex = 0xF0F1F2F3;
 int bit_i, i;
 int total_bits = sizeof(hex) * 8;
 printf("Conversão de 0x%X:\n",hex);
 for(i=total_bits-1;i>=0;i--){
 bit_i = is_bit_um(hex, i) ? 1 : 0;
 printf("%d",bit_i);
 if( (i % 4 == 0) && (i>0)){
 printf(".");
 }
 }
 printf("\n");
 return 0;
}

No programa mostra_em_bin.c (Listagem 19), a função is_bit_um devolve i) zero se o bit num_bit do parâmetro valor é zero e ii) não zero (valor lógico verdadeira) se o bit num_bit for um. Para o efeito, a função atribui à variável mascara_num_bit um bit a um na posição pretendida através da operação de deslocamento à esquerda, aplicando posteriormente a máscara através da operação de AND binário. No exemplo, a função é chamada sucessivamente para mostrar cada um dos bits da variável hex, disponibilizando assim a representação binária do valor da variável hex como ilustra a Listagem 20.

Ativação/desativação seletiva de bits

Como o nome sugere, a ativação seletiva de bits consiste em colocar um ou mais bits a um. A desativação seletiva de bits corresponde à operação inversa, isto é, colocar um ou mais bits a zero.

A ativação seletiva de bits efetua-se através da operação de OR binária, usando como operandos o valor que se pretende modificar e uma máscara apropriada. A máscara deve ser constituída por bits a zero, exceto para os bits que se pretendem ativar, que devem estar a um. Por exemplo, caso se pretenda ativar os 4 bits menos significativos de um valor inteiro, deve-se empregar como máscara o valor binário que tenha os quatro bits menos significativos a 1111, estando os restantes a zero. Deste modo, e considerando um valor de 16 bits, a máscara corresponderá ao valor 0x000F, ativando-se os 4 bits menos significativos através da operação: novo_valor = valor | 0x000F.

A desativação seletiva de bits é conseguida através da operação de AND binária, usando como operadores, o valor que se pretende alterar e uma apropriada máscara binária. A máscara binária deve ser composta por bits a zero nas posições que se pretendem desativar e bits a um nas restantes posições. Por exemplo, caso se pretendam desativar os 4 bits menos significativos de um valor de 16 bits, usar-se-á a máscara 0xFFF0, resultando na seguinte operação: novo_valor = valor & 0xFFF0.

Deteção de valores potências de dois

Determinar se o valor de uma determinada variável inteira sem sinal corresponde a uma potência de dois é uma operação trivial quando se recorre a operações binárias. De facto, dado que uma potência de dois tem um e só um bit a um (e.g., 16 que é 0001.0000 em binário), subtraindo-se uma unidade à potência de dois, obtém-se um valor que tem todos os bits à direita do bit ativo da potência de dois a um, e a zero o bit ativo bem como todos os bits à esquerda do bit ativo da potência de dois. Por exemplo, subtraindo-se 1 unidade a 16 obtém 15, correspondendo a 0000.1111 em binário. Assim, para determinar se um determinado valor é uma potência de dois, basta efetuar uma operação de AND binário entre o valor e valor menos uma unidade. Se o resultado for zero, o valor em apreço é uma potência de dois. É importante notar que este algoritmo para averiguar se determinado inteiro é uma potência de dois só é válido para valores positivos. A função is_potencia_dois (Listagem 21) faz uso dessas propriedades das potências de dois para detetar se parâmetro valor corresponde ou não a uma potência de dois. A saída da execução do programa is_potencia_dois é mostrada na Listagem 22.

/*
 * Exemplo: operações binária para averiguar
 * se número positivo é potência de dois.
 * "Manipulação de bits na linguagem C" 
 * Revista Programar 
 * Patricio R. Domingues
 */
#include <stdio.h>
int is_potencia_dois(unsigned int valor){
 if( valor == 0 || valor == 1 ){
 return 0;
 }
 return ((valor & (valor-1)) == 0? 1:0);
}
int main(void){
 unsigned int i;
 for(i=2;i <= (1<<10); i++){
 if( is_potencia_dois(i) ){
 printf("%u\n", i);
 }
 }
 return 0;
}

Ativação de opções

Algumas funções da linguagem C requerem o uso da operação de OR binário por forma a que seja possível especificar múltiplas opções através de um parâmetro. Um exemplo é a função open que é empregue para a abertura de um ficheiro. Conforme mostra a Listagem 23, a função apresenta dois parâmetros. O primeiro corresponde ao caminho do ficheiro que se pretende manipular. Mais interessante para o âmbito deste artigo, é o segundo parâmetro, designado de flags, pois permite a especificação de vários elementos. De facto, a documentação da função open (e.g., man 2 open num sistema Linux) indica que podem ser especificada, entre outros, constantes para a criação de um ficheiro. Por exemplo, a criação de um ficheiro somente para escrita é especificada através de O_CREAT | O_WRONLY | O_TRUNC, isto é, especificando-se as opções O_CREAT, O_WRONLY e O_TRUNC através do operador OR binário. O valor que é efetivamente recebido pela função open corresponde pois ao resultado da operação de OR binário das três constantes. Na prática, as três constantes são potências de dois, significando que cada uma apenas têm um bit ativo. Tal é confirmado pelo programa open_flag.c (Listagem 24) que mostra o valor numérico das constantes O_CREAT, O_WRONLY e O_TRUNC (Listagem 25). Deste modo, torna-se possível passar, através de um mesmo parâmetro, várias configurações, sendo cada configuração especificada por um ou mais bits. Contudo, é necessário ter em conta que esta metodologia de empacotamento em bits de configurações requer código do lado da função chamada para que essa possa identificar as configurações pretendidas pela função chamante.

int open(const char *pathname, int flags);

/*
 * Mostra o valor numérico de algumas das constantes
 * que podem ser empregues pela função open
 */
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
int main(void){
 printf("O_WRONLY = %X\n", O_WRONLY);
 printf("O_CREAT = %X\n", O_CREAT);
 printf("O_TRUNC = %X\n", O_TRUNC);
 return 0;
}

Notas finais

A manipulação ao nível do bit é algo que os programadores da linguagem C devem conhecer por forma a tirar o melhor partido da linguagem. Embora o seu uso explícito seja mais comum na programação de baixo nível, o exemplo da função open ilustra que a manipulação ao nível de bit, embora de forma implícita, ocorre frequentemente na linguagem C.

Para quem tem necessidade de recorrer à manipulação ao nível do bit, é ainda importante ter em conta os problemas, uns mais subtis do que outros, que podem ser encontrados. É exemplo disso o uso da operação de deslocamento à direita, cujo comportamento varia consoante o compilador e a plataforma que se está a usar.

Bibliografia

1. Baraniuk, C. (05/05/2015). The number glitch that can lead to catastrophe. Obtido de BBC: http://www.bbc.com/future/story/20150505-the-numbers-that-lead-to-disaster
2. Open-STD. (2003). Rationale for International Standard — Programming Languages — C. Obtido de http://www.open-std.org/JTC1/SC22/WG14/www/C99RationaleV5.10.pdf
3. Steele, G. L. (1977). Arithmetic shifting considered harmful. ACM SIGPLAN Notices, 11 (12), 61–69. Obtido de http://dspace.mit.edu/bitstream/handle/1721.1/6090/AIM-378.pdf