*6. a) Mostre que este algoritmo determina o número de bits 1 na cadeia S :
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, S-1 é a cadeia de bits obtida trocando-se o bit 1 mais à direita de S por um 0 e todos os bits 0 à direita deste por 1s. [Lembre-se de que S \wedge(S-1) é o operador AND de S e S-1.]
b) Quantas operações com operadores A N D são necessárias para encontrar o número de bits 1 em uma cadeia S ?

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, contagem é exatamente o número de bits 1 em S e (b) quantas operações AND \wedge são feitas.

Passo 2

Ao subtrair 1 de S em representação binária, o bit 1 mais à direita em S vira 0 e todos os bits 0 à direita desse bit viram 1. Por exemplo, se
S = \dots1001000_2,
então
S - 1 = \dots1000111_2.
Quando fazemos
S := S \wedge (S-1),
o efeito é apagar (zerar) o bit 1 mais à direita de S, porque esse bit é 1 em S e 0 em S-1, e manter todos os bits à esquerda dele. Seguindo o exemplo,
\dots1001000_2 \;\wedge\; \dots1000111_2 \;=\;\dots1000000_2,
ou seja, exatamente um 1 a menos.

Passo 3

Cada iteração do laço incrementa contagem em 1 e elimina um bit 1 de S. O laço só termina quando S=0, ou seja, quando não restam mais bits 1. Logo, ao sair do while, contagem é igual ao número inicial de bits 1 em S. Isso prova a correção do algoritmo.
Em cada iteração ocorre exatamente uma operação AND \wedge. Como o número de iterações é igual ao número de bits 1 de S, o total de operações AND necessárias é justamente o número de bits 1 em S.

Resposta

(a) O procedimento conta corretamente os bits 1 em S porque cada passo apaga exatamente um bit 1 e incrementa contagem.
(b) São necessárias tantas operações AND quanto houver bits 1 em S.

Exercícios de Livros Relacionados