src/integer/misc/cl_I_power2p.cc

   1 // power2p().
   2
   3 // General includes.
   4 #include "cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cl_integer.h"
   8
   9
  10 // Implementation.
  11
  12 #include "cl_I.h"
  13 #include "cl_DS.h"
  14
  15 uintL power2p (const cl_I& x) // x > 0
  16 {
  17 // Methode 1: Wenn ord2(x) = integer_length(x)-1.
  18 // Methode 2: Wenn logand(x,x-1) = 0.
  19 // Methode 3: Wenn das erste Digit /=0 eine Zweierpotenz ist und alle weiteren
  20 //            Digits Null sind.
  21         if (fixnump(x))
  22           { var uintL x_ = FN_to_UL(x);
  23             if (!((x_ & (x_-1)) == 0)) return 0; // keine Zweierpotenz
  24             integerlength32(x_,return); // Zweierpotenz: n = integer_length(x)
  25           }
  26           else
  27           { var const uintD* MSDptr;
  28             var uintC len;
  29             var const uintD* LSDptr;
  30             BN_to_NDS_nocopy(x, MSDptr=,len=,LSDptr=); // normalisierte DS zu x bilden.
  31             var uintD msd = mspref(MSDptr,0);
  32             if (msd==0) { msshrink(MSDptr); msd = mspref(MSDptr,0); len--; }
  33             // len = Anzahl der Digits ab MSDptr, len>0, msd = erstes Digit (/=0)
  34             if (!((msd & (msd-1)) == 0)) return 0; // erstes Digit muß Zweierpotenz sein
  35             if (DS_test_loop(MSDptr mspop 1,len-1,LSDptr)) return 0; // danach alles Nullen
  36            {var uintL msdlen;
  37             integerlengthD(msd, msdlen=);
  38             return intDsize*(uintL)(len-1) + msdlen; // integer_length(x) als Ergebnis
  39           }}
  40 }