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

[ken.rietz@asbury.edu]

Ah, math. My strong suit! :-)

Showing $_&$_-1 == 0 only when $_ is a power of 2 is not hard,
once you see the trick. (Then again, a whole lot of FWP is easy once
you see the trick.) This assumes that $_ is positive, to avoid
the 0&-1 == 0 problem.

Thinking is terms of least significant bit is a red herring.
Think instead of the most significant (but still non-zero) bit.
The only time that $_ and $_-1 do not share the same highest power of
2 is when $_ is a power of 2. So, if $_ is not a power of two, then
$_&$_-1 will have that (common) highest power of 2 bit set, and
therefore not be zero.

-- Ken Rietz

> 
> Actually, there is still a bug in the $_&$_-1 logic.  Not only does it
> work for positive powers of 2, it also (falsely) reports that 0 is a
> power of 2 (i.e. 0&-1 == 0).
> 
> As to a formal proof, I don't know enough math to be able to 
> state it in
> all the proper terms, etc., but it seems to me that the only 
> time that a
> positive binary integer does not share any bits with its 
> predecessor is
> when, for lack of a better phrase, "the odometer rolls over" 
> (e.g. from
> 00001111 to 0001000), and that only happens for a power of two.  Any
> math guru want to put this in better terminology? :)
> 
> JH
> 
> Jeff Pinyan wrote:
> > 
> > On May 1, Jeff Helman said:
> > 
> > >>   if (YOUR CODE HERE) { print "$_ is a power of 2" }
> > >     if (YOUR CODE HERE) { print "$_ is NOT a power of 2" }
> > >
> > >then $_&$_-1 would match your 7.  So I'll bite, what was 
> your 7? (Of
> > >course, you can send it to me privately if you don't want 
> to spoil it
> > >quite yet.)
> > 
> > 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? :)
> > 
> > -- japhy
> 
> ==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
> ==== Send email to <fwp-request@technofile.org> with message _body_
> ====   unsubscribe
> 

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