首页 > 代码库 > o(1)取与n二进制 1个数的相等且 最小的 大于n 的数

o(1)取与n二进制 1个数的相等且 最小的 大于n 的数

给你一个uint32 a,让你找到另一个uint32 b,使b > a,且b的二进制中1的个数等于a二进制中1的个数。且使b最小。(数据保证可出)

1 因为1的个数不变,所以必然大于n+lowbit(n);(lowbit(int n){return n&-n;}//取n的最小一个100000串,也就是取最后一位二进制1),先得到ripple=n+lowbit(n);

2 这个时候改变的1个数,取one=ripple^n;one里面有改变的1个数n1,再加上新增位一共n1+1个1,那么把one向后调lowbit长度+2,得到n1-1个1 且最后一个1是紧贴2^0位的,也就是最后一位

3 因为ripple的最后lowbit长度都是0,直接加上即可

 

int getthenum(int n){    int lowbit=n&-n;    int ripple=n+lowbit;    int one=ripple^n;    one=(one>>2)/lowbit;    return ripple|one;}