Comparing sequences with range objects
Antoon Pardon
antoon.pardon at vub.be
Sun Apr 10 16:20:33 EDT 2022
Op 9/04/2022 om 02:01 schreef duncan smith:
> On 08/04/2022 22:08, Antoon Pardon wrote:
>>
>> Well my first thought is that a bitset makes it less obvious to calulate
>> the size of the set or to iterate over its elements. But it is an idea
>> worth exploring.
>>
>
>
>
> def popcount(n):
> """
> Returns the number of set bits in n
> """
> cnt = 0
> while n:
> n &= n - 1
> cnt += 1
> return cnt
>
> and not tested,
>
> def iterinds(n):
> """
> Returns a generator of the indices of the set bits of n
> """
> i = 0
> while n:
> if n & 1:
> yield i
> n = n >> 1
> i += 1
>
Sure but these seem rather naive implementation with a time complexity of
O(n) where n is the maximum number of possible elements. Using these would
turn my O(n) algorithm in a O(n^2) algorithm.
--
Antoon Pardon.
More information about the Python-list
mailing list