收集n（的Python，C++）的2功率分解

Question

我寫一個快速程序分解一個數字2的冪這是一種有效的方式做到這一點：

pows=[] 
    pos = 0 
    while n>0: 
     if n%2==1: pows.append(2**pos) 
     n/=2 
     pos+=1 

我已經用Python編寫的，但我也對如何在C++中完成它感興趣。

我不知道這是否是一種「聰明」的方式來做到這一點，或者它被認爲是非常低效的。

Answer 1

在C++中最自然的實現將使用一個位掩碼爲兩個 的權力，是這樣的：

std::vector<unsigned> p2; 
unsigned m = 1; 
while (m != 0) { 
    if ((m & i) != 0) { 
     p2.push_back(m); 
    } 
    m <<= 1; 
} 

你肯定不希望每次調用pow功能 循環。一個有點掛羊頭賣狗肉的方式，這很可能更快 （因爲它通常會通過在循環減倍）將是：

std::vector<unsigned> p2; 
std::cout << i << ": "; 
while (i != 0) { 
    unsigned n = i & i - 1; 
    p2.push_back(i^n); 
    i = n; 
} 

我建議第一（這是很容易理解的） 除非探查真的說你必須使用第二個。

Answer 2

任何現代編譯器可能會足夠聰明，以優化這一點。首先讓你的代碼正確運行，並且在分析後優化速度（如果速度太慢）。