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

[Michael Assels <mjassels@cs.concordia.ca>]

		       On Mon, 01 May 2000 13:12:47 EDT,
			      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? :)

By definition, powers of 2 have only a single 1-bit in their binary
representations.  Everything else has at least two 1-bits.  Let X be
a non-power-of-2.  Then X's binary representation must have as a suffix
a string of the form

	10.......010.......0
         ^^^^^^^^^ ^^^^^^^^^
          M zeros   N zeros

where M, N >= 0.

If N == 0, then X-1 just flips the least significant bit of X, so
both X and X-1 have a 1 in the leftmost position of the suffix.
Therefore (X & X-1) is non-zero.

If N > 0, then the binary representation of X-1 must have as a suffix 
a string of the form


	10.......001.......1
         ^^^^^^^^^ ^^^^^^^^^
          M zeros   N ones

In this case, too, both X and X-1 have a 1 in the leftmost position
of the suffix.  Therefore (X & X-1) is non-zero.  QED

Michael

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