Path: utzoo!attcan!utgpu!utstat!jarvis.csri.toronto.edu!mailrus!umich!sharkey!atanasoff!hascall
From: hascall@atanasoff.cs.iastate.edu (John Hascall)
Newsgroups: comp.lang.c
Subject: Re: sqroot of a 2**n number ?
Message-ID: <1094@atanasoff.cs.iastate.edu>
Date: 13 May 89 15:24:39 GMT
References: <1906@yunexus.UUCP>
Reply-To: hascall@atanasoff.cs.iastate.edu (John Hascall)
Organization: Iowa State Univ. Computation Center
Lines: 55

In article <1906@yunexus.UUCP> oz@yunexus.UUCP (Ozan Yigit) writes:
>given any number that is an exact power of two, finding the square
>root: this can be done by counting to the bit position on some
>architectures. Does anyone know of a really portable version of
>this, assuming the code below will not work on all architectures ?
>(no sqrt call)
 
>	if (n > 0)	/* n > 0 && n == 2**X */
>		for (i = 0; !(n & 1); i++)
>			n >>= 1;
 
  By an amazing coincidence, I happen to have just written something
  of a similar nature--everyone can feel free to use it (or take potshots
  at it).

  John Hascall

-------------------- cut here ---------------------------------------
/*
** HIBIT        - find the highest set bit in an int, this can be used
**                      as a quick base-2 logarithm.
**
**      John Hascall / 12-May-1989
**
** Description:  This algorithm uses a divide and conquer strategy and is
**      O(log n), n the number of bits.  The routine works by dividing   
**      the int, v,  in half and testing that half, this continues until 
**      the last half (2 bits) is tested.  Note that if no bits are set  
**      zero is returned.
**
**      Hint: m goes: 0xffffffff, 0x0000ffff, 0x00ff00ff, 0x0f0f0f0f,
**                    0x33333333, 0x55555555
*/

#define HALF    16              /* one half of the number of bits in an int */

unsigned int hibit( v )
unsigned int v;
{
        int             i;                      /* size of chunks to test */
        unsigned int    m;                      /* mask used to divide v */ 
        unsigned int    s;                      /* hibit accumulated sum */ 

        s = 0;
        m = ~0;                                 /* all ones (0xffffffff) */
        for ( i = HALF; i > 0; i >>= 1 ) {
                m ^= (m << i);  
                if (~m & v) {   
                        s |= i; 
                        v >>= i;
                }   
        }           
        return( s );
}
-------------------------- end -------------------------------------