设某算法中设有一个无符号32位整型变量count=b<sub>31</sub>b<sub>30</sub>...b<sub>1</sub>b<sub>0</sub>,其功能是作为计数器,不断地递增(count++,溢出后循环),每经一次递增,count的某些比特位都会在0和1之间转。

比如,若当前有:<img src='https://img2.soutiyun.com/ask/2021-01-27/980606673475979.jpg' /> 则下次递增之后将有:<img src='https://img2.soutiyun.com/ask/2021-01-27/980606682370488.jpg' /> 在此过程中,共有(最末尾的)三个比特发生翻转。 现在,考查对c连续的足够多次递增操作。纵观这一系列的操作,试证明: a)每经过2^k次递增,b<sub>k</sub>恰好翻转一次; b)对于每次递增操作,就分摊的意义而言,count只有o(1)个比特位发生翻转。

时间:2023-10-03 13:44:40

相似题目