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

[Ken Scott <kscott-list@pcisys.net>]

On Mon, 1 May 2000, 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? :)
> 

I can talk around it, but I can't do it mathematically (it's been WAAAAY
too long ago for that).

If the value is a power of two, it's binary representation will consist of
a single 1 bit and all other positions are 0. When you subtract 1 from the
value, the bit that was a value of 1 becomes 0 and all 0 bits below become
1's. Thus, when you & the values, you will get either 0 & 0 or 1 & 0 for
every bit position, giving 0 as a result.

For the non-power of two values, at least one bit position will be a 1 and
remain a 1 after the subtraction. Thus, when the & is performed there will
be at least one 1 & 1, which guarantees a non-zero result, which Perl
interprets as a true value.

I know, there is a short, sweet mathematical proof for this, and I would
love to see it :)

Ken

-- 
><>   Ken Scott   kscott@pcisys.net   http://www.pcisys.net/~kscott   
                                                                      
              This is the day that the Lord has made;             
              I will rejoice and be glad in it!          -- Psalm 118:24  


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