[算法题]将一个正整数分解为2的n次方之和

任意一个正整数,都可以分解成2的n次方的和(不知道数学上的叫法是什么?)

如:

func(1) = 2⁰;

func(2) = 2¹

func(3) = 2¹+2⁰

func(5) = 2²+2⁰

func(7) = 2²+2¹+2⁰

func(8) = 2³;

.

.

func(65) = 2⁶+2⁰

 

php的解法:

 

function func1($num){
    $res = array();
    while($num>0){
        $re = pow(2, floor(log($num,2)));
        $num -= $re;
        $res[] = $re;
    }
    return $res;
}
?>

 

在网友rardge的提示下,我想出了第二种方法,不过估计这并不是rardge所说的方法,因为效率比我原来的还差..

 

二进制位判断法:

 

function func2($num){
    $bit = decbin($num);
    $pow = array_reverse(str_split($bit));
    foreach($pow as $k=>$v) {
        if($v==1) $re[] = pow(2,$k);
    }
    return $re;
}

两种方法的效率对比:

//benchmark
//1
function testFunc1($nums){
    foreach($nums as $v) func1($v);
}
//2
function testFunc2($nums){
    foreach($nums as $v) func2($v);
}

require_once 'Benchmark/Iterate.php';

$benchmark1 = new Benchmark_Iterate;
$benchmark1->run(1000, 'testFunc1',$nums);
$benchmark2 = new Benchmark_Iterate;
$benchmark2->run(1000, 'testFunc2',$nums);


$result = $benchmark1->get();
echo 'func1:'.$result["mean"]."
";
$result = $benchmark2->get();
echo 'func2:'.$result["mean"]."
";

结果:

func1:0.000229
func2:0.000328

原来的方法稍胜一点...