sqroot of a 2**n number ?
John Hascall
hascall at atanasoff.cs.iastate.edu
Sun May 14 01:24:39 AEST 1989
In article <1906 at yunexus.UUCP> oz at 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 -------------------------------------
More information about the Comp.lang.c
mailing list