La multiplication Utilisation au niveau du bit Opérateurs de décalage Giving TLE

Question

Question

Étant donné N et M, écrire une équation à l'aide des opérateurs de décalage gauche dont le résultat sera égal au produit N * M.

Entrée: La première ligne a 0 < T ≤ 50000 indiquant le nombre de cas de test.
Suivant T lignes ont deux entiers 0 < N, M ≤ 10¹⁶.

sortie: Pour chaque cas d'essai pour imprimer une équation N * M ressemblant

(N < < p1) + (N < < p2) + ... + (N < < pk) où p1 ≥ p2 ≥ ... ≥ pk et k est le minimum.

SAMPLE INPUT SAMPLE OUTPUT 

2 
2 1    (2<<0) 
2 3    (2<<1) + (2<<0) 

Limite de temps: 1,0 sec

Ma solution 1ère approche

int dig = (int)(Math.floor(Math.log10(m)/Math.log10(2))+1); 
boolean flag = false; 
for(long i = dig; i>=0; --i) {  
     if(((m>>(i-1l)) & 1l) == 1l) { 
      if(flag) 
       System.out.print(" + ("+n+ "<<"+(i-1)+")"); 
      else { 
       System.out.print("("+n+"<<"+(i-1)+")"); 
       flag = true; 
       } 
      } 
     } 

Deuxième approche

boolean[] arr = new boolean[dig]; 
     int i = dig-1; 
     while(m > 0) { 
      if((m&1) == 1) { 
       arr[i] = true; 
      } 
      i--; 
      m = m>>1l; 
     } 
     int j = dig-1; 
     for(i = 0; i < dig; ++i) { 

      if(arr[i]) { 
       if(flag) 
       System.out.print(" + ("+n+"<<"+j+")"); 
       else { 
        System.out.print("("+n+"<<"+j+")"); 
        flag = true; 
       } 
      } 

      j--; 
     } 

Dans les deux cas que je reçois 5 correcte sur 8 et reste 3 sont TLE pourquoi?

Answer 1

Je ne vois pas quoi que ce soit dans vos deux approches qui empêchent une dizaine de milliers de produits-de numéros jusqu'à 57 bits pour être représenté comme String s en une seconde:
TLEpeut être due à la prise System.out.print() une quantité de temps démesurée.
Cela dit, utiliser un utilitaire comme

/** builds <code>n * m</code> in the form 
    * <code>(n&lt;&lt;p1) + (n&lt;&lt;p2) + ... + (n&lt;&lt;pk)</code> 
    * using left shift. 
    * @param n (0 < multiplicand <= 10**16) 
    * @param m 0 < multiplier <= 10**16 
    * @return a verbose <code>String</code> for <code>n * m</code> 
    */ 
    static String verboseBinaryProduct(Object n, long m) { 
     int shift = Long.SIZE - Long.numberOfLeadingZeros(m) - 1; 
     final long highest = 1 << shift; 
     final StringBuilder binary = new StringBuilder(42); 
     final String chatter = ") + (" + n + "<<"; 
     final long rest = highest - 1; 
     while (true) { 
      if (0 != (highest & m)) 
       binary.append(chatter).append(shift); 
      if (0 == (rest & m)) { 
       binary.append(')'); 
       return binary.substring(4); 
      } 
      m <<= 1; 
      shift -= 1; 
     } 
    } 

et System.out.println(verboseBinaryProduct(n, m));.