NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/comp/programm/2044

Internet Message Format | 1992-07-21 | 3.1 KB

Path: sparky!uunet!olivea!hal.com!decwrl!cache.crc.ricoh.com!james
From: [e-mail] (James Allen)
Newsgroups: comp.programming
Subject: Re: finding 1st one in integer
Summary: Mimimal modulus not always prime
Message-ID: <[e-mail]>
Date: 22 Jul 92 01:30:18 GMT
References: <[e-mail]> <[e-mail]>
Organization: RICOH California Research Center
Lines: 97

In article <[e-mail]>
    [e-mail] (Andy Lowry) writes:
] [someone else asks:]
] > I need a very efficient way of finding the first bit set ( doesn't matter
] > which side ) in a 32 bit integer.
]
] > One can make the simplifying assumption that only 1 bit will be
] > set in the 32 bit integer (if that helps).

Or take the slightly more difficult case where at most 1 bit is set.
Call this case "ALLOWZERO".

]This seems to work nicely:
]
]int firstone(x)
]unsigned int x;
]{
]  static int keys[] = {
]    -1,  0,  1, 26,  2, 23, 27, -1,  3, 16,
]    24, 30, 28, 11, -1, 13,  4,  7, 17, -1,
]    25, 22, 31, 15, 29, 10, 12,  6, -1, 21,
]    14,  9,  5, 20,  8, 19, 18 };
]
]  return keys[x % 37];
]}
]
]The idea is that you want to use a table lookup, but not on the entire
]sparse range 1-2^31, so you need to find a hash function that will map
]the set {2^n: 0 <= n <= 31} uniquely to a reasonably dense range of
]integers.  Using remainder modulo 37 does the trick, and the table
]above was generated by a trivial C program.  The -1 entries are
]unused.
]
]There's probably some algebraic way of predicting what divisor to use
]instead of 37 to get the minimum sized table for a given "word size,"
]but I'll leave that for somebody else to fill in.  I just started with
]33 and tried successive numbers until one worked...

We may need some help from sci.math to get the algebraic solution,
but I followed Andy's approach for all wordsizes up to 490:

       Wordsize        Minimum Modulus
       2               2 (or 3 if ALLOWZERO)
       3                4 (or 5 if ALLOWZERO)
       4               5
       5 -    6           9
       7 -   10          11
      11 -   12          13
      13 -   18          19
      19 -   20          25
      21 -   28          29
      29 -   36          37
      37 -   52          53
      53 -   58          59
      59 -   60          61
      61 -   66          67
      67 -   82          83
      83 -  100         101
     101 -  106         107
     107 -  110         121
     111 -  130         131
     131 -  138         139
     139 -  148         149
     149 -  162         163
     163 -  172         173
     173 -  178         179
     179 -  180         181
     181 -  196         197
     197 -  210         211
     211 -  226         227
     227 -  268         269
     269 -  292         293
     293 -  316         317
     317 -  346         347
     347 -  348         349
     349 -  372         373
     373 -  378         379
     379 -  388         389
     389 -  418         419
     419 -  420         421
     421 -  442         443
     443 -  460         461
     461 -  466         467
     467 -  490         491

]        ...But I don't believe
]it can be a coincidence that 37 is the least prime greater than 32!

Well, 17 is the least prime greater than 13.
There are four nonprimes in the above "Minimal Moduli" although
they are all squares of primes: 4, 9, 25, 121.

]--
]Andy Lowry, [e-mail], [phone]
]IBM Research, P.O. Box 704, Yorktown Heights, NY  10598

James Allen, [e-mail]