*6. a) Mostre que este algoritmo determina o número de bits 1 na cadeia
:
procedure contagem de bit (S: cadeia de bits)
contagem \(:=0\)
while \(S \neq 0\)
begin
contagem \(:=\) contagem +1
\(S:=S \wedge(S-1)\)
end \{contagem é o número de 1s em \(S\) \}
Aqui,
é a cadeia de bits obtida trocando-se o bit 1 mais à direita de
por um 0 e todos os bits 0 à direita deste por 1s. [Lembre-se de que
é o operador AND de
e
.]
b) Quantas operações com operadores
são necessárias para encontrar o número de bits 1 em uma cadeia
?
procedure contagem de bit (S: cadeia de bits)
contagem \(:=0\)
while \(S \neq 0\)
begin
contagem \(:=\) contagem +1
\(S:=S \wedge(S-1)\)
end \{contagem é o número de 1s em \(S\) \}
b) Quantas operações com operadores
Passo 1
O enunciado apresenta o procedimento
procedure contagem de bit (S: cadeia de bits)
contagem :\(=0\)
while S \(\neq 0\)
begin
contagem := contagem \(+1\)
S := S ∧ (S - 1)
end
e pede (a) mostrar que, ao final, e (b) quantas operações AND
são feitas.
contagem
é exatamente o número de bits 1 em
Passo 2
Ao subtrair 1 de
em representação binária, o bit 1 mais à direita em
vira 0 e todos os bits 0 à direita desse bit viram 1. Por exemplo, se
então
Quando fazemos
o efeito é apagar (zerar) o bit 1 mais à direita de
, porque esse bit é 1 em
e 0 em
, e manter todos os bits à esquerda dele. Seguindo o exemplo,
ou seja, exatamente um 1 a menos.
Passo 3
Cada iteração do laço incrementa . O laço só termina quando
, ou seja, quando não restam mais bits 1. Logo, ao sair do . Isso prova a correção do algoritmo.
Em cada iteração ocorre exatamente uma operação AND . Como o número de iterações é igual ao número de bits 1 de
, o total de operações AND necessárias é justamente o número de bits 1 em
.
contagem
em 1 e elimina um bit 1 de
while
, contagem
é igual ao número inicial de bits 1 em
Em cada iteração ocorre exatamente uma operação AND
Resposta
(a) O procedimento conta corretamente os bits 1 em
porque cada passo apaga exatamente um bit 1 e incrementa
(b) São necessárias tantas operações AND quanto houver bits 1 em .
contagem
.(b) São necessárias tantas operações AND quanto houver bits 1 em