NTTL Function - FactorPowerOfTwo

Description

Remove the powers of 2 from a number.  Return the odd number, and the power of 2 removed.  Mathematically:

Compute K s.t. A = K * 2^e; return K and e.

Header

<nttl/factorPowerOfTwo.h>

Signature

template< class T, class T2 >
T FactorPowerOfTwo( T A, T2 *e )

Parameters

Name	Type	Description
A	T	The number from which to remove the powers of 2.
e	T2	A pointer to the variable that will contain the powers of 2.

Returns

( T )  A with the powers of two removed.  An odd number.

Example

#include <nttl/factorPowerOfTwo.h> ... long A = 212312; short e; long K = FactorPowerOfTwo( A, &e ); // // Now K = ?, and e = ? //

Notes

This algorithm works by right shifting the number until it is odd.  For some multi-precision integer types, it may be more efficient to first determine how many powers of two exist (using bit masks, for instance), then shifting the number only once.   Hence it may be desirable to specialize this function for particular types.