**To**:**fwp@technofile.org****Subject**:**Re: [FWP] Golf (7 strokes is par!)****From**:**Ilmari Karonen <iltzu@sci.fi>**- Date: Wed, 3 May 2000 13:49:32 +0300 (EET DST)
- In-Reply-To: <Pine.SOL.3.96.1000501205210.18096B-100000@simpukka>

On Mon, 1 May 2000, Ilmari Karonen wrote: > On 1 May 2000, Ariel Scolnicov wrote: > > Jeff Pinyan <jeffp@crusoe.net> writes: > > > Challenge: determine if $_ is an integral power of 2 (1,2,4,8,16,...) > > > I have it down to 7 characters. Can anyone beat that? > > > > print"$_ is a power of 2"unless$_&$_-1; > > Another answer with 7 strokes: $_&~-$_ > > Six strokes seems impossible to me - I'll get back as soon as my > exhaustive search finishes.. Well, it did finish at last. No 6-stroke answers, but I did find a third 7-stroke solution. All three are listed below - there are of course also three more trivial solutions obtained by swapping the operands for &. 1. $_ & $_ - 1 2. $_ & ~ - $_ 3. $_ & $_ / 3 The first answer is Jeff's original, and proof of its correctness has already been given. The second is identical to the first assuming ones' complement arithmetic, since ~$x == -$x - 1. The third answer is a bit more interesting. It is trivially obvious that it must evaluate to zero whenever $_ is a power of 2. To prove that the converse is true, we'll begin by assuming that the number has been shifted right enough that the second highest set bit is the LSB. This lets us consider only numbers of the form 2**n + 1, where n is a positive integer. We must prove that for all n ((2**n + 1) / 3) & 1 is non-zero, that is, that the LSB remains set even after the division. The following two statements are equivalent to the one above: ((2**n + 1) / 3) % 1 >= 1 (2**n + 1) % 6 >= 3 This is true if n == 1, since 2**n + 1 == 3. Now, if a == 2**n + 1, then 2**(n+1) + 1 == 2*a - 1, and also (2**(n+1) + 1) % 6 == (2*a - 1) % 6. Building a table of all the possible values, we see that: a % 6 == 0 => (2*a - 1) % 6 == 5 a % 6 == 1 => (2*a - 1) % 6 == 1 a % 6 == 2 => (2*a - 1) % 6 == 3 a % 6 == 3 => (2*a - 1) % 6 == 5 (*) a % 6 == 4 => (2*a - 1) % 6 == 1 a % 6 == 5 => (2*a - 1) % 6 == 3 (*) The lines marked with (*) indicate that, if (2**n + 1) % 6 belongs to the set {3, 5}, then so will (2**(n+1) + 1) % 6. Since we have shown that this is true for (2**1 + 1) % 6, by induction it must hold for all n, QED. -- Ilmari Karonen http://www.sci.fi/~iltzu/ ==== Want to unsubscribe from Fun With Perl? Well, if you insist... ==== Send email to <fwp-request@technofile.org> with message _body_ ==== unsubscribe

**References**:**Re: [FWP] Golf (7 strokes is par!)***From:*Ilmari Karonen <iltzu@sci.fi>

- Prev by Date:
**Re: [FWP] Golf (7, er 16 strokes is par!)** - Next by Date:
**Re: [FWP] Counting bits from the other end** - Prev by thread:
**Re: [FWP] Golf (7 strokes is par!)** - Next by thread:
**Re: [FWP] Golf (7 strokes is par!)** - Navigation:
**Date Index | Thread Index | Search | Other lists at bumppo.net**