这题是宁波区域赛的热省赛中的一题……
后来偶然发现时POJ上的,而且有人用位运算搞过了,于是就去学位运算,通过Matrix67大牛的三篇文章学的,第四篇还没看,(想看的可以去搜下Matrix67或者去我前面的文章找下,应该是sgu那篇,可以找到链接)
这题可以这么想,比如原数x=0101110的下一个是01100011,你可以这样想,以要比原数大,必须把原数的最右边的一段1(连续的,如果只有一个的,就是一个)变成0,把这段1的右边的第一个0变成1,然后再在所得的数的最右边补1,知道1的位数一样。
这样的话,我们就可以这样做了
设原数为x
然后t = x + (x & -x);//(x & -x) 取x的最右边的一个1,因为"把原数的最右边的一段1变成0"可以加上最右边一个1
接下来就是补1的过程了,当然可能不用补
好吧我们用一个函数得到x(10进制)在2进制表示下的1的个数(如果有看不懂的,建议先看下Matrix67大牛的位运算在看,当然到那个时候基本你自己也可以写了,不必要看我的了,呵呵)
函数如下
get

这样我们就基本是完成了。具体代码如下,个人建议先自己想,实在想不出来之后再看我的代码
CODE