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

[Duncan Booth]

Tim Rowe <digitig at gmail.com> wrote:

> 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!
> 
> 
I meant the bitwise twiddling, but actually I misread it. I thought Mark 
was using the n&~n+1 trick to pull out bits from least significant upwards 
when of course he's just clearing the low bit not extracting it.


-- 
Duncan Booth http://kupuguy.blogspot.com