Frage Das Quadrat einer Zahl finden


Ich habe diese Frage gefunden,

schreibe eine Funktion, die ein Quadrat der gegebenen Ganzzahl n ohne Multiplikation zurückgibt.

Lösung dafür 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 macht, aber ich verstehe nicht, warum das funktioniert.

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


5
2018-02-18 07:54


Ursprung


Antworten:


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

100 * 111

Offensichtlich wurde nur 111 um zwei nach links verschoben: 11100

Dieser Code macht das für jedes Bit, das 1 in ist iund summiert die Ergebnisse. So dreht sich zum Beispiel 111 * 111 in

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

Die Multiplikation auf diese Weise zu teilen, ist erlaubt, weil Multiplikation über Addition verteilt wird, das macht was 001 * 111 + 010 * 111 + 100 * 111 gleich (001 + 010 + 100) * 111und jetzt ist es offensichtlich gleich 111 * 111.


5
2018-02-18 08:04