有人在itpub上出了这么一道题

5bit数: 二进制中包含5个1的数,例如11111,1011011,100011101...

要求如下:
输入任意十进制a,b 参数, a<b,b<1000000000
(1)求出a,b 之间的最小5bit数
(2)求出a,b 之间所有5bit数的和

性能要求:输入50组测试用例,总消耗时间不能超过3s

1.直接法
由网友solomon_007 最先回答。但他的写法需要Oracle12才能支持,所以,把它改写成一个函数+一个sql,并用了2个绑定变量。

create or replace function fn_10to2(p_num number) return varchar2
is
   l_str varchar2(32767):=null;
   n1 number;
   n2 number;
begin
   n1 := p_num;
   loop
     n2 := mod(n1, 2);
     n1 := trunc(n1 / 2);
     l_str := to_char(n2) || l_str;
     exit when n1 = 0;
   end loop;
   return l_str;
end fn_10to2;
/

var a number
var b number
exec :a:=10000
exec :b:=200000

SQL> with t as (select level n,fn_10to2(level)v from dual connect by level <=:b)
  2  select min(n),sum(n) from t where regexp_count(v,'1')=5 and n between :a and :b;

              MIN(N)               SUM(N)
-------------------- --------------------
               10000            543234109

已用时间:  00: 00: 04.75

仅一个测试用例就不满足时间要求了。 经过分析,以上算法的问题出在太多的无效测试,假定范围是0-31*2^5,最多有10个二进制位,每个位都可能为0和1,因此刚好5位的数量大约占1/10。另外9/10都是无效测试。
2.间接法
这种算法先求长度为0-b的长度所有5bit数,然后计算那些落在a和b之间的数。这相当于在指定长度的位上求5个1的组合,而2进制长度与数值是以2为底的对数关系。时间复杂度从O(n)降低为O(log n)。

SQL> with t as(select power(2,level-1)a from dual connect by level<=ceil(log(2,:b)))
  2  ,r as(select a.a+b.a+c.a+d.a+e.a v
  3  from t a,t b,t c,t d,t e
  4  where a.a<b.a and b.a<c.a and c.a<d.a and d.a<e.a)
  5  select min(v),sum(v) from r where v>=:a and v<=:b;

              MIN(V)               SUM(V)
-------------------- --------------------
               10000            543234109

已用时间:  00: 00: 00.07

SQL> exec :a:=0

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.03
SQL> exec :b:=1000000000

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00
SQL> /

              MIN(V)               SUM(V)
-------------------- --------------------
                  31       25476202472250

已用时间:  00: 00: 00.85

可见,算法2比算法1快,而且b越大,越明显。