Re: [FWP] Golf (7 strokes is par!)

[Nathan Torkington <gnat@frii.com>]

Jeff Pinyan writes:
> Yes, I am a foolish stupid scum.  My mistake.  You are right with
>   $_&$_-1
> Do you happen to have the proof for why that is 0 for ONLY powers of 2? :)

Consider a number $n as $b+$r, where $b is the largest power of two
less than the number, and $r is the rest.  For example, 131 is 128 +
3.  If $r is <0, the $b+$r representation of $n-1 has the same $b
(131-1 == 130, which is 128+2).

When you AND together these numbers, the $b bit will be set in the
answer because it's present in both the anderands.  Therefore when
$n is not a power of two, $n&$n-1 is not zero.

For a power of two, however, $n-1 yields a smaller $b and a $r that
has all bits set.  $n and $n-1 thus have no bits in common, so $n&$n-1
is 0 when $n is a power of two.

Not sure how acceptable that proof would be to my combinatorics
prof, but it'll do for FWP :-)

Nat

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe