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

[Jeff Pinyan <jeffp@crusoe.net>]

>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).

Well of course.  This was meant for positive integers, as my proof below
clarifies.

>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? :)

Proof that

  N & (N - 1) = 0

if AND ONLY IF N is 2**M, where M is a non-negative integer:

  All positive integers, when in binary representation, end in a 1
  followed by zero or more 0's.

    examples:
      ...1000
        ...10
         ...1

  When 1 is subtracted from this number, the right-most 1 becomes a 0,
  and all the trailing 0's after it become 1's.

    examples:
      ...0111
        ...01
         ...0

  If there are any 1's before that 1 that was changed to a 0, then

    N & (N-1)

  results in a non-0 number, and since N is not in the form of a single 1
  followed by zero or more 0's, N is not a power of 2.

  If there are NO 1's before the 1 that was changed to a 0, then

    N & (N-1)

  is 0, and N is a power of 2, since it is of the form of a single 1
  followed by zero or more 0's.

-- 
MIDN 4/C PINYAN, NROTCURPI, US Naval Reserve             japhy@pobox.com
http://www.pobox.com/~japhy/                  http://pinyaj.stu.rpi.edu/
PerlMonth - An Online Perl Magazine            http://www.perlmonth.com/
The Perl Archive - Articles, Forums, etc.    http://www.perlarchive.com/


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