Suppose that we count, in binary, using an nn-bit counter that goes from 00 to 2

Question

Suppose that we count, in binary, using an nn-bit counter that goes from 00 to 2n1. There are 2n steps: the initial step and then 2n1 increment steps. Observe that each increment step causes at least one bit to be changed. As a function of n, what is the average number of bit flips that occur per step? (Count the initial step of setting all n bits to zero as n flips.) For example, n=3, we have 000001010011100101110111

which is 3+1+2+1+3+1+2+1=14 total flips for an average of 14/8=1.75 bit flips per step. Prove your answer.

Explanation / Answer

for 3 bits we have 14changes

for 4 bits
when MSB is fixed we get 14 changes 2 time (onece when MSB is 1, and another when MSB is 0) and MSB changes twice, so there will be total of 30changes

so total number of changes for n bits =
   f(n) = 2*f(n) + 2 or
         = 2*(f(n) + 1)

f(1) = 2
f(2) = 2*(2 + 1)
f(3) = 2*(2*2 + 2 + 1)
f(4) = 2*(2*2*2 + 2*2 + 2 + 1)
...
f(n) = 2*2^n - 2

therefore avg: (2*2^n - 2) / (2^n) = 2-1/2^(n-1)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.