Сбор разложение 2-мощности п (Python, C++)

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

Любой современный компилятор, вероятно, будет достаточно умным, чтобы его оптимизировать. Сначала убедитесь, что ваш код работает правильно, и беспокоиться об оптимизации скорости после профилирования (если он слишком медленный).