首页 > 代码库 > D - A or...or B Problem

D - A or...or B Problem

题意:给定A,B,问[A,B]里取任意个数按位或,结果有多少种。

思路:这题需要找出一个分界点,即找到最高位的B是1,A是0的位置x(最低位从0开始),那么对于所有OR的结果,x处要么是1要么是0,x是0有多少种呢?这里就需要从[A,1<<x)里挑选数进行OR,即有(1<<x)-A种,因为A到(1<<x)-1都可以表示出来;x处为1有几种呢?有两种情况①从(1<<x, B]里挑选,结果就不说了依此类推,②从上述两个区间都挑选,那就是也是(1<<x)-A种,然后上述两种两种情况可能会有重复,需要判断去重,最后判读是否要加上(1<<x)这一种就行了

D - A or...or B Problem