Suche Quadrat einer Zahl

Question

Ich habe diese Frage,

schreiben Sie eine Funktion, die ein Quadrat der angegebenen Ganzzahl n ohne Multiplikation zurückgegeben.

Lösung ist

public static int sq(int n){ 
     int i = n; 
     int sq = 0; 
     int count = 0; 

     while(i > 0){ 
      if((i & 1) == 1){ 
       sq += n << count; 
      } 

      i = i >> 1; 
      count++; 
     } 

     return sq; 
    } 

Ich verstehe, was die Funktion tut, aber ich verstehe nicht, warum dies funktioniert.

Kann jemand erklären, warum das eine funktionierende Lösung ist?

Answer 1

Weil Multiplikation über Addition verteilt wird. Das klingt wahrscheinlich mysteriös, aber das ist wirklich der Grund. Betrachten Sie diese Multiplikation:

100 * 111 

Offensichtlich, dass nur 111 von zwei nach links verschoben: 11100

Dieser Code macht, dass für jedes Bit, das 1 in i ist, und die Ergebnisse summiert werden. So ist es zum Beispiel dreht 111 * 111 in

001 * 111 = 00111 
010 * 111 = 01110 
100 * 111 = 11100 
      ----- + 
      110001 

Splitting die Multiplikation auf diese Weise erlaubt, da Multiplikation über hinaus vertreibt, ist das, was 001 * 111 + 010 * 111 + 100 * 111 gleich (001 + 010 + 100) * 111 macht, und jetzt ist es offenbar gleich 111 * 111.