题目内容
(请给出正确答案)
[主观题]
设某算法中设有一个无符号32位整型变量count=b31b30...b1b0,其功能是作为计数
器,不断地递增(count++,溢出后循环),每经一次递增,count的某些比特位都会在0和1之间转。
比如,若当前有:
则下次递增之后将有:
在此过程中,共有(最末尾的)三个比特发生翻转。
现在,考查对c连续的足够多次递增操作。纵观这一系列的操作,试证明:
a)每经过2^k次递增,bk恰好翻转一次;
b)对于每次递增操作,就分摊的意义而言,count只有o(1)个比特位发生翻转。
查看答案
如果结果不匹配,请 联系老师 获取答案