CommonIntAlgo

Files CCore/inc/algon/CommonIntAlgo.h CCore/src/algon/CommonIntAlgo.cpp

Here is two Algorithm Packages with some useful integer algorithms.

BitIntAlgo

This package is parametrized by an unsigned integral type. It contains three algorithms.

template <class UInt>
struct Algon::BitIntAlgo
 {
  static bool IsEven(UInt a);
  
  static unsigned BitScan(UInt a); // a!=0
  
  static UInt OddPart(UInt a); // a!=0
 };

IsEven() returns true, if the argument is even.

BitScan() returns the number of zero least significant bits of the argument, which must not be zero. In other words, it is the maximum exponent of the power of two, which divides the argument.

OddPart() returns the "odd part" of the argument, which must not be zero. "Odd part" is the maximum odd divisor of the number. Each non-zero number is a product of its "odd part" and a power of two.

CommonIntAlgo

This package contains algorithms to calculate GCD (great common divisor) and LCM (least common multiple). The first template parameter is the argument type of algorithms. It must be an unsigned integral type. The second is an algorithm package, defaulted to the BitIntAlgo<UInt>.

template <class UInt,class Algo=Algon::BitIntAlgo<UInt> >
struct Algon::CommonIntAlgo : Algo
 {
  static UInt GCD(UInt a,UInt b);
  
  static UInt LCM(UInt a,UInt b); // no overflow check
 };

Functions

There are two functions to calculate GCD and LCM for unsigned integral arguments:

template <class UInt>
UInt Algon::GCD(UInt a,UInt b) { return Algon::CommonIntAlgo<UInt>::GCD(a,b); }

template <class UInt>
UInt Algon::LCM(UInt a,UInt b) { return Algon::CommonIntAlgo<UInt>::LCM(a,b); }

They call the correspondent algorithms from the CommonIntAlgo.