Using while loop and if statement to tell if a binary has an odd or even number of 1's.

Tim Rowe digitig at gmail.com
Thu Feb 5 11:10:31 CET 2009


2009/2/5 Duncan Booth <duncan.booth at invalid.invalid>:
> Mark Dickinson <dickinsm at gmail.com> wrote:
>
>> def count_set_bits(n):
>>     # make sure we include an if, to
>>     # satisfy OP's requirements:
>>     if n < 0:
>>         raise ValueError
>>     count = 0
>>     while n:
>>         count += 1
>>         n &= n-1
>>     return count
>>
>> is_even = count_set_bits(the_int) % 2 == 0
>>
>> ...but anyone submitting this as a homework
>> solution had better be prepared to explain why
>> it works.
>>
>
> I remember a programming exercise when I was an undergraduate and anyone
> who *didn't* use that trick got marked down for writing inefficient code.

Is adding and a modulus *really^ more efficient than flipping a bool
as I suggested? I think I'd want to see measurements!


-- 
Tim Rowe



More information about the Python-list mailing list