SPUG: Cool power-of-2 trick

[Michael R. Wolf]

While reading through the perl-quiz-of-the-week, I noticed this neat test 
to find if a number is a power of 2.  Originally, I didn't even believe it 
worked so I wrote a little program to test it.  The program helped me 
figure out that it does, in deed, work, and *how* it works.  If a number is 
a pure powere of 2, it only has one bit set.  If you subtract 1 from it you 
have to borrow from that bit, effectively clearing it and setting all the 
bits below it.  If you then bitwise-and the two numbers, you're guaranteed 
to come up with zero.  You can't get zero otherwise.  Coooool.


foreach $n (1 .. 2<<8) {
     if (( $n & ($n-1)) == 0){
         printf "%4d %10b %10b %10.10b\n" => $n, $n, $n-1, $n&($n-1);
     }
}
  $n          $n        $n   $n & $n-1
decimal  binary    binary      binary
    1          1          0 0000000000
    2         10          1 0000000000
    4        100         11 0000000000
    8       1000        111 0000000000
   16      10000       1111 0000000000
   32     100000      11111 0000000000
   64    1000000     111111 0000000000
  128   10000000    1111111 0000000000
  256  100000000   11111111 0000000000
  512 1000000000  111111111 0000000000



Michael R. Wolf
     All mammals learn by playing!
         MichaelRWolf at att.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.pm.org/pipermail/spug-list/attachments/20050120/46ded945/attachment-0001.htm