[FWP] Counting bits from the other end

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

The recent mention of the old a&(a-1) trick reminds me of a programming 
problem that I've _never_ [over a lot of years, in a lot of languages] 
found a really good solution for [it is the reason why, back when, I took 
just amused note that DEC had added JFFO to the pdp-6 instruction set]:

a & (a-1) turns off the lowest-order bit in a (binary) number.  Can you 
find some reasonable way to turn off the *highest* order bit in the 
number?  Best I could find was to do the a&(a-1) in a loop and just 
remember the last-nonzero-value... but it'd sure be neat if there was a 
trick to find that bit directly without the loop...

==========================================
On a related matter, from a real-world example [although at the time I 
solved the problem in assembler, the technique maps forward], one of the 
reasons we old-timers needed to do this kind of bit-twiddling was because 
we often read "status words" from I/O devices or subsystem controllers 
and the hardware generally just set bits in the status word to mean this 
or that.  One thing was a mask of pending operations and you needed to 
process them one at a time...

Finding the individual bits is easy enough --- you go one step beyond the 
current hack to do:

     a XOR (a AND (a-1))

and that gets you _just_one_ bit from a [or zero if there are no bits 
left in a].  Then you needed to answer the question "which bit do I 
have".  The simple code just does a shift-loop until the bit goes away, 
but I have a deeply inbred dislike for loops when straight-code will do 
the job and so I implemented a simple, direct way to convert the power-of-
2 to "which bit was that" [at that point you could dispatch through a 
dispatch table to the approrpriate handler, and then come back to look at 
'a' again to check for the next thing-to-do].

The solution I came up with used division remainders.  At the time I was 
programming the PDP-1, which had 18-bit words and I noticed that if you 
take the 18 powers-of-two and divide them by _nineteen_ you get all-
distinct remainders [plus, as a nice benefit, zero gets you a remainder 
of zero so you don't even need to test for zero!]  So you calculate the 
remainders then sort-by-remainder [that is, you start with a real simple 
array:
   array[n] = remainder when (2^n) is divided by 19
then you sort by remainders so that you get:
   newarray[n] = power of two that gets you a remainder of 'n'..etc..

then you get to write the code:

     handler = dispatch[(a xor (a and a-1)) mod 19]

and leave it as a mystery for future generations of programmers as to 
what the hell you were doing (and heaven help them if they mess with the 
dispatch table).  Appropriate divisors for 36-bit [and 16- and 32-bit] 
numbers is left as an exercise..:o)

Oh well, enough reminiscing...

  /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