首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。