src/integer/misc/cl_I_ord2.cc

   1 // ord2().
   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 // Methode 1a:
  18 //   Sei n = ord2(x). Dann ist logxor(x,x-1) = 2^n + (2^n-1) = 2^(n+1)-1.
  19 //   Also  (ord2 x) = (1- (integer-length (logxor x (1- x)))) .
  20 // Methode 1b:
  21 //   Sei n = ord2(x). Dann ist logand(x,-x) = 2^n.
  22 //   Also  (ord2 x) = (1- (integer-length (logand x (- x)))) .
  23 // Methode 1c:
  24 //   Sei n = ord2(x). Dann ist lognot(logior(x,-x)) = 2^n-1.
  25 //   Also  (ord2 x) = (integer-length (lognot (logior x (- x)))) .
  26 // Methode 2:
  27 //   Nullbits am Schluß von x abzählen:
  28 //   (ord2 x) = intDsize * Anzahl der Nulldigits am Schluß
  29 //              + Anzahl der Nullbits am Ende des letzten Digits /=0.
  30
  31 uintC ord2 (const cl_I& x) // x /= 0
  32 {
  33         if (fixnump(x))
  34           { var uintV x_ = FN_to_V(x); // x als intVsize-Bit-Zahl
  35             // This assumes cl_value_len <= intVsize.
  36             #if (intVsize>32)
  37             ord2_64(x_,return);
  38             #else
  39             ord2_32(x_,return);
  40             #endif
  41           }
  42           else
  43           { var uintC bitcount = 0;
  44             var const uintD* ptr;
  45             BN_to_NDS_nocopy(x, ,,ptr=); // normalisierte DS zu x bilden.
  46             while (lspref(ptr,0) == 0) { lsshrink(ptr); bitcount += intDsize; } // Nulldigits abzählen
  47             var uintD lsd = lspref(ptr,0); // letztes Digit /=0
  48             ord2_D(lsd,bitcount +=); // dessen Nullbits abzählen
  49             return bitcount;
  50           }
  51 }
  52
  53 }  // namespace cln