How can I group numbers by their powers of two in Python?
Asked by
MellowCedar47
I have a list of numbers such as [16, 17, 19, 20, 22, 23, 24, 26, 28, 29, 31, 32]. I want to identify numbers based on their factorization into an odd factor and a power of two, then place matching values into separate groups. For example, I may want one group for numbers divisible by 2², another for 2³, and so on, without knowing in advance how many groups will be needed. The solution should work for larger ranges, such as 64 through 128, and should avoid manually creating a separate variable for every possible group.
Answers
If you only need to select powers of two, a bitwise test is convenient: n > 0 and (n & (n - 1)) == 0. For a general list of matching values, use that predicate with filter() or a list comprehension. Keep in mind that filtering only selects values; it does not organize them into multiple groups, so a dictionary is still needed for the grouping part.
Reply to this answer
This is more of a grouping problem than a sorting problem. A useful approach is to repeatedly divide each number by 2 until the remaining value is odd. That remaining odd value can be used as the dictionary key, while the original numbers become the values in each group. This automatically creates as many groups as necessary.
Reply to this answer
You can also group by the exponent of 2, which tells you how many times the number is evenly divisible by 2. For example, 20 is 5 × 2², so its exponent is 2; 24 is 3 × 2³, so its exponent is 3. A dictionary or defaultdict is a better fit than creating lots of separately named lists.
Reply to this answer
Add your answer
Answers are reviewed before publication.
MellowCedar47: That makes sense. I was thinking in terms of separate lists, but using a dictionary would let the program create the groups dynamically.