功能强大!高效!简单易懂组合位操作
本篇摘要
本篇介绍一个非常给力的求组合的算法!上一篇“c_c++刁钻问题各个击破之位运算及其实例(2)”介绍了6个比较复杂的位操作,但是没有给出任何应用实例,本篇就之前谈到的位操作进行应用,其主要内容是用位操作来实现求组合。
引例
先来看一道题目,这个题目是理解利用位操作求组合的关键。它是POJ的2453。英文原题就不贴了,我用中文描述一下吧:给定一个正整数N,求最小的、比N大的正整数M,使得M与N的二进制表示中有相同数目的1。
上面的题目描述或许有点拗口,举个例子把,假如给定的N为78,其二进制表示为1001110,包含4个1,那么最小的比N大的并且二进制表示中只包含4个1的数是83,其二进制是1010011,因此83就是答案。那么如何求解这个问题呢?这里给出两个思路:
(1) 最直观的思路:枚举
思路是从N+1开始枚举,对每个数都测试其二进制表示中的1的个数是否与N的二进制表示中1的个数相等,遇到第一次相等时就停止。其算法流程如下:
1、 求得N的二进制表示中1的个数k;
2、 N++;
3、 测试N的二进制表示中所包含的1的个数是否等于k,如果是,则输出N后结束,否则转2;
上面的过程可以用如下的流程图来表示:
用代码实现上述流程如下:
int GetNextN(unsigned int N)
{
int k = count1Bits(N);
do
{
N++;
}while(count1Bits(N)!=k);
return N;
}
上面的代码中还有一个问题没有解决,那就是“求整数的二进制表示中有多少个1”即count1Bits()函数。这个问题在我之前的《c/c++刁钻问题各个击破之位运算及其实例(1)》中有详细阐述,它应用了n&=(n-1)能将n的二进制表示中的最右边的1翻转为0的事实。只需要不停地执行n&=(n-1),直到n变成0为止,那么翻转的次数就是原来的n的二进制表示中1的个数,其代码如下:
int count1Bits(unsigned int n)
{
int count = 0;
while(n)
{
count++;
n&=(n-1);
}
return count;
}
至此,第一个枚举方法介绍完毕,你只需要写如下的main()函数就能测试本方法:
void main()
{
int N;
cin>>N;
cout<<
推荐阅读
-
功能强大!高效!简单易懂!查找组合的位运算--引例
-
功能强大!高效!简单易懂组合位操作
-
像首席技术官一样思考:如何高效管理 30 人的研发团队?-管理越多越轻松。好的研发团队,应该是上拨下用,即下级对上级的向上管理;而不是反过来,总是向下管理,甚至是 CTO 做经理的事,经理做工程师的事,工程师最终会被当成实习生。如果是这样,就会越管越累,不仅团队无法成长,而且团队整天很忙还效率低下,问题一大堆。 有这样一个小故事:一位高级经理下班后帮忙倒垃圾,结果被老板训斥了一顿。这就好比首席技术官做了实习生自己该做的事。事情本身没有对错之分,只是从不同的角度有不同的理解。 古人云:"用人不疑,疑人不用"。在面对自己的研发团队时,应该相信他们能做好,授权一线开发人员充分发挥专业特长,不要限制他们的工作。但在相信他们的同时,也要进行二次确认,始终秉持 "我相信,但我要确认 "的原则和严谨的精神。因为每个人都会犯错和疏忽,通过发挥团队的智慧,团队犯错的机会就会大大减少。比如回归测试、代码审查、开发演示、变更审批等等。 如前所述,每个人都难免会犯错。但作为管理者,你所设计和商定的流程不能出错。管理者的每一个决定和沟通都应该经过深思熟虑。就像红绿灯的交通设计,某辆车不小心闯红灯可能会扣分,但红绿灯的设计一定要正确、人性化、统一。再比如,开发人员可能会因为疏忽大意写出 bug,但研发流程的设计和上线流程的发布不能有任何差错。因此,流程体系的设计,一方面要结合当前团队规模、业务特点和需要重点解决的问题来设计,另一方面也要在人员防错、效率提升、发挥团队集体智慧等维度进行综合考量。应该站在更高更抽象的角度去思考,不断思考一个倍受欢迎的园区应该如何设计,思考一个灵动、经典、永恒的建筑应该遵循怎样的模式,思考一个成功、优秀、卓越的研发团队应该需要怎样的流程和制度。 最后,反馈很重要。向上汇报很重要,向下反馈也很重要。能够保持顺畅的双向反馈和闭环管理,对研发团队的协作和沟通有着非常明显的积极作用。在向上汇报方面,要培养团队在正式汇报、会议汇报、私下沟通、书面总结、非正式场合等方面的沟通能力,提醒下属报喜也要报忧。凡事先记录,再跟进,最后反馈。反馈很重要,主动汇报更难得。 另一方面,同时也不要忽视向下反馈。好的爱,是双向的。团队也是如此,没有严格的上下级之分,只是分工和角色不同而已。作为管理者,不必总保持一种 "神秘感",让人 "捉摸不透 "才是牛。当团队做得好或有人做得好时,要记得在公开或私下场合给予肯定和赞许。业务有增长、业绩有提升时,别忘了给团队一些鼓励,或者安排一次下午茶或聚餐。在例会或正式会议上,也可以同步向大家传达一些重要信息和高层指示。"欲速则不达,欲远则同行"。 当向上汇报、向下反馈的沟通闭环形成后,同时结合前面研发过程的管理闭环,双管齐下,就能形成良性循环。如此反复,持之以恒,优秀卓越的研发团队,必将呈现。 能力、产出和效率 接下来,继续重复关于能力、产出和效率的话题。 站在不同的角色,以及一个企业经营、生存和发展所需要的基础上,我把研发生产力分为三个层次,分别是:一线员工关心的研发能力、管理层关心的软件产出和操作人员关心的企业生产效率。简单概括就是:既要把工作做好,又要能出成果,还要能帮企业赚钱。