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

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

)
如:
func(1) = 20;
func(2) = 21
func(3) = 21+20
func(5) = 22+20
func(7) = 22+21+20
func(8) = 23;
.
.
func(65) = 26+20

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
原来的方法稍胜一点...