src/integer/misc/cl_I_power2p.cc

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