Gabarito da Lista 1

Computadores e Programação (MAB-353)
Primeira Lista de Exercı́cios Individual v.0
100 pontos
Prof. Paulo Aguiar (DCC/IM/UFRJ)- GABARITO
Questão 1 Exercı́cio 2.65 do livro. (20 pontos) Tradução do enunciado: Escreva um código para implementar a seguinte função:
/* Retorna 1 quando x contém um número ı́mpar de uns; 0 caso contrário. Assuma w=32. */
int odd ones(unsigned x);
Sua função deve seguir as regras de codificação ao nı́vel de bit para inteiros (página 120), exceto que você
pode assumir que o tipo int tem w = 32 bits. O seu código pode conter um máximo de 12 operações bit a
bit aritméticas e lógicas.
Solução: Para detetar um número ı́mpar de bits uns em uma palavra de 32 bits, assumindo bi como o
valor do bit da posição i, 0 ≤ i ≤ 31, tenho que computar b0 ⊕ b1 · · · ⊕ b31 .
Mas para fazer isso em menos de 12 operações, temos que quebrar o valor x de 32 bits em duas partes,
digamos x1 e x2 , calcular p16 = x1 ⊕ x2 , bit a bit, reduzindo para 16 bits. Fácil ver que p1 6 = [b31 ⊕ b15 , b30 ⊕
b14 , · · · , b16 ⊕ b0 ].
Repetindo o processo, pode-se obter
p8 = [b31 ⊕ b15 ⊕ b23 ⊕ b7 , b30 ⊕ b14 ⊕ b22 ⊕ b6 , · · · , b24 ⊕ b8 ⊕ b16 ⊕ b0 ]
p4 = [b31 ⊕ b15 ⊕ b23 ⊕ b7 ⊕ b27 ⊕ b11 ⊕ b19 ⊕ b3 , · · · , b28 ⊕ b12 ⊕ b20 ⊕ b4 ⊕ b24 ⊕ b8 ⊕ b16 ⊕ b0 ]
p2 = [b31 ⊕ b15 ⊕ b23 ⊕ b7 ⊕ b27 ⊕ b11 ⊕ b19 ⊕ b3 ⊕ b29 ⊕ b13 ⊕ b21 ⊕ b5 ⊕ b25 ⊕ b9 ⊕ b17 ⊕ b1 ,
b30 ⊕ b14 ⊕ b22 ⊕ b6 ⊕ b26 ⊕ b10 ⊕ b18 ⊕ b2 ⊕ b28 ⊕ b12 ⊕ b20 ⊕ b4 ⊕ b24 ⊕ b8 ⊕ b16 ⊕ b0 ], e finalmente
p1 = b31 ⊕ b15 ⊕ b23 ⊕ b7 ⊕ b27 ⊕ b11 ⊕ b19 ⊕ b3 ⊕ b29 ⊕ b13 ⊕ b21 ⊕ b5 ⊕ b25 ⊕ b9 ⊕ b17 ⊕ b1 ⊕ b30 ⊕ b14 ⊕ b22 ⊕
b6 ⊕ b26 ⊕ b10 ⊕ b18 ⊕ b2 ⊕ b28 ⊕ b12 ⊕ b20 ⊕ b4 ⊕ b24 ⊕ b8 ⊕ b16 ⊕ b0 ], ou seja, p1 é o ou-exclusivo de todos os
bits de x e o valor a ser retornado.
O código C da rotina é dado abaixo, lembrando que o deslocamento à direita para unsigned é lógico:
int odd_ones (unsigned x) {
unsigned p16 = (x >> 16) ^ x; /* Xor bits i e i+16 para 0 <= i
unsigned p8 = (p16 >> 8) ^ p16; /* Xor bits i and i+8 for 0 <=
unsigned p4 = (p8 >> 4) ^ p8; /* Xor bits i and i+4 for 0 <= i
unsigned p2 = (p4 >> 2) ^ p4; /* Xor bits i and i+2 for 0 <= i
unsigned p1 = (p2 >> 1) ^ p2; /* Xor bits 0 and 1; lixo nos 31
return p1 & 1; /* retorna o valor no LSB apenas, desprezando o
1
< 16; lixo nos 16 bits superiores */
i < 8; lixo nos 24 bits superiores */
< 4; lixo nos 28 bits superiores */
< 2; lixo nos 30 bits superiores */
bits superiores */
lixo */
Questão 2 Exercı́cio 2.66 do livro. (20 pontos) Tradução do enunciado: Escreva um código para implementar a seguinte função:
/* Gere uma máscara que indica a posição do 1 mais à esquerda. Assuma w=32.
Por exemplo 0XFF00 − > 0x8000, e 0x6600 −− > 0x4000.
Se x=0, então retorne 0. */
int lefmost one (unsigned x);
Sua função deve seguir as regras de codificação ao nı́vel de bit para inteiros (página 120), exceto que você
pode assumir que o tipo int tem w = 32 bits. O seu código pode conter um máximo de 15 operações bit a
bit aritméticas e lógicas. Dica: Primeiro transforme x num vetor da forma [0 ... 011 ... 1].
A dica aponta para a solução. Assumindo bi o valor do bit na posição i,
ao se fazer x = x|(x >> 1), obtemos
x = [b31 |b31 , b31 |b30 , b30 |b29 , b29 |b28 , · · · , b2 |b1 , b1 |b0 ].
Observe que se b31 = 1, então as duas posições superiores do resultado ficariam em 1. Se b31 = 0, então
a ocorrência de 1 em b31 |b30 dependerá do valor de b30 , ou seja, as duas posições mais significativas terão 1
a partir do bit mais à esquerda de x em 1.
Fazendo em seguida x = x|(x >> 2), obtemos
x = [b31 |b31 , b31 |b30 , b31 |b30 |b29 , b31 |b30 |b29 |b28 , b30 |b29 |b28 |b27 , · · · , b4 |b3 |b2 |b1 , b3 |b2 |b1 |b0 ].
As quatro posições mais significativas terão 1 a partir do bit mais à esquerda de x em 1.
Fazendo em seguida x = x|(x >> 4), as 8 posições mais significativas terão 1 a partir do bit mais à
esquerda de x em 1. Fazendo em seguida x = x|(x >> 8), as 16 posições mais significativas terão 1 a partir
do bit mais à esquerda de x em 1. Fazendo em seguida x = x|(x >> 16), as 32 posições terão 1 a partir do
bit mais à esquerda de x em 1, e teremos obtido a máscara da dica.
Para de fato gerar a resposta pretendida, falta o passo xˆ= (x >> 1), que zera todos os bits da máscara
anteriormente obtida, exceto na posição do bit 1 de x mais à esquerda.
O código C é dado abaixo, com 12 operações bit a bit:
int leftmost_one(unsigned x) {
/* Obtém a máscara da dica no formato [0...011...1] */
x |= (x>>1);
x |= (x>>2);
x |= (x>>4);
x |= (x>>8);
x |= (x>>16);
/* Deixa agora apenas o bit 1 mais à esquerda */
x ^= (x>>1);
return x;
}
Questão 3
Exercı́co 2.69 do livro.(20 pontos)
Tradução do enunciado: Escreva o código para uma função com o seguinte protótipo:
/* Faça um deslocamento circular à esquerda. Assuma 0 ≤ n < w. * Exemplos quando x = 0x12345678 e w
= 32: * n = 4 − > 0x23456781, n = 20 − > 0x67812345 */
unsigned rotatel ef t(unsignedx, intn);
2
Sua funç~
ao deve seguir as regras de codificaç~
ao ao nı́vel de bit para inteiros (página 120).
Cuidado para o caso de n=0.
Soluç~
ao: O resultado será a composiç~
ao de duas partes: a esquerda e a direita.
unsigned rotate_left (unsigned x, int n) {
/* Quando n=0, cria máscara com todos os bits em 1; todos em 0, caso contrário. */
int mascara = -!n; /* Lembrar que -1 s~
ao todos os bits em 1 */
/* Desloca n bits à esquerda para posicionar a rotaç~
ao e gerar espaço para os n bits inferiores. */
/* Obtem os w-n bits inferiores na posiç~
ao certa */
unsigned esquerda = x << n;
/* Desloca w-n bits à direita para posicionar adequadamente os n bits superiores de x na rotaç~
ao */
/* Desloca o número de bits adequado */
unsigned direita = x >> ((sizeof(unsigned) << 3)-n);
/* Se máscara for só de 1s é porque n=0 e retorna x; */
/* Se for só de 0s, retorna a concatenaç~
ao de esquerda e direita */
return (mascara & x) | (mascara & (esquerda|direita));}
Questão 4 Exercı́cio 2.71 do livro. (20 pontos) Tradução do enunciado: Você acabou de iniciar trabalhando
em uma companhia que está implementando um conjunto de rotinas para operar sobre uma estrutura de
dados onde 4 bytes com sinal estão empacotados em um tipo unsignes de 32 bits. Bytes dentro da palavra
sÃo numerados de 0 (LSB) a 3 (MSB). Você foi designado para desenvolver uma função para uma máquina
operando com complemento a 2 e deslocamentos à direita aritméticos com o seguinte protótipo:
/* Declaração de tipo onde 4 bytes são empacotados em um tipo unsigned. */
typedef unsignes packed t;
/* Extrair byte da palavra. Retorna um inteiro com sinal. */
int xbyte (packed t word, int bytenum);
Isto é, a função extrai o byte designado e estende o sinal para ser representado como um inteiro de 32
bits. O seu antecessor (que foi despedido por incompetência) escreveu o seguinte código:
/* Tentativa fracassada de xbyte */
int xbyte (packed_t word, int byteenum) {
return (word >> (bytenum << 3)) & 0xFF;
A. O que está errado com este código?
R: O deslocamento a esquerda equivale a multimplicar por 8. Caso se pretenda extrair um byte qye represente
um valor negativo, o deslocamento à direita estará sempre inserindo bits à esquerda dependendo apenas valor
do bit 31, o que não é a extensão de sinal desejada. Os 24 bits superiores do resultado deveriam ter o sinal
do MSB do byte alvo.
B. Dê uma implementação correta da função que usa apenas deslocamentos à direita e à esquerda, junto
com uma única subtração.
R: A ideia é deslocar o byte alvo até a posição 3 e depois deslocar à direita 24 posições, fazendo a extensão
de sinal com o deslocamento aritmético.
int xbyte(packed_t word, int bytenum) {
int left = word << ((3-bytenum) << 3); /* desloca à esquerda para posicionar corretamente */
/* o byte alvo na posiç~
ao 3 */
return left >> 24; /* desloca byte alvo para a posiç~
ao 0, estendo corretamente o sinal */}
3