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

["Bernie Cosell" <bernie@fantasyfarm.com>]

On 1 May 2000, at 13:12, Jeff Pinyan wrote:

> ... You are right with
> 
>   $_&$_-1
> 
> Do you happen to have the proof for why that is 0 for ONLY powers of 2? :)

I posted this trick back in the early days of FWP...  it is a very old 
assembly-language programmers trick... I remember using it in the bowels 
of the I/O service routines of a timesharing system I worked on in the 
mid 1960s.   That was when I learned it, taught to me by my predecessor 
[who was about to leave BBN to go back to school for a PhD].

As for a 'proof', it depends on how rigorous you want to be.  If you take 
a base-2 positive number, you can ask the question "how do I subtract one 
from such a number".

The answer is easy to prove by induction:

To subtract one from a positive non-zero number you:

  for bit-position [power-of-2] 0 to N:
     complement bit
     exit loop if you just complemented a 0 to a 1

this is very easy to prove as formally as you want.  Once you have *THIS* 
definition of what it means to subtract 1, then the rest is easy:
    a & (a-1)

will have zeros in every bit position form the lowest-order-bit up 
through the first nonzero bit [reason:  for those bit postions, a and a-1 
have complementary bits; the last (highest order) such bit position has a 
1 complemented to a zero, all the others have 0s complemented to 1s].  
*above* that bit position [as per the 'exit' in the loop above] a and a-1 
are identical.

The statement of the answer is very simple:

     a & (a-1)    Turns off the lowest-order bit in a

and given the above analysis it is almsot trivial to do a simple 
inductive proof of this.


Now, back tot he problem at hand: once yo have proven the above, then the 
current question is even more than trivial:

    if (a & (a-1)) equals zero, then by the previous theorem, that 
implies that there must have be *exactly* one non-zero bit in a, which 
implies that a was a power of two.  QED..

  /Bernie\
-- 
Bernie Cosell                     Fantasy Farm Fibers
mailto:bernie@fantasyfarm.com     Pearisburg, VA
    -->  Too many people, too few sheep  <--          

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