// mulN.cpp
// ------------  Version 21.04.2008
//               Model: beliebig
//               char:  beliebig
//               D.Schwarzer, www.GoBlack.de

// Thema: Multiplikation durch Schieben nach rechts und links 


#include <stdio.h>                    // für printf()
#include <conio.h>                    // für getch(), wenn benötigt


// mulN
// Die Funktion multipliziert zwei positive ganze Zahlen vom Typ
// unsigned in fak1 und fak2 durch Schieben nach rechts. Das
// Ergebnis wird als unsigned long zurückgegeben.
unsigned long mulN(unsigned fak1, unsigned fak2)
{
  unsigned long lfak1=fak1;  // Wandlung von fak1 in unsigned long
  unsigned long erg=0;       // Ergebnisspeicher

  unsigned  t2= 0;           // Faktor als Vielfaches von 2^n
  int        n= 0;           // Zähler der Schiebeoperationen

  if (!fak2) return(0);                  // Multiplikation fak2=0
  do{
     t2= 1;
     // in n feststellen wie oft fak2 durch 2,4,8 .. 2^n teilbar
     // ist und den Faktor t2 als Vielfaches von 2^n bestimmen.
     // war fak2=24, ist n=4 und f2=16 => Rest 24-16 =8 und es
     // folgt ein zweiter Durchlauf der Schleife mit 8  
     for(n=0; (fak2>>1)>=t2; n++) t2=t2<<1;
     // fak1 2^n fach multiplizieren
     erg= erg+(lfak1<<n);
     // Unterschied zum tatsächlichen Faktor fak2 feststellen und
     // wenn noch ein Unterschied besteht, den Rest in einem
     // weiteren Umlauf bearbeiten.
     fak2= fak2-t2;
    }while(fak2);
  return(erg);
}


// main()
// das Testprogramm ruft die Funktion mulN() mit den beiden
// Faktoren fak1 und fak2 auf und gibt das Ergebnis zum Bildschirm
// aus.
void main(void)
{
  unsigned fak1= 65535;
  unsigned fak2= 32769;
  unsigned long ergebnis= 0;

  ergebnis= mulN(fak1, fak2);
  printf("\r\nLoesung von %u x %u = %lu", fak1, fak2, ergebnis);
  getch();
}