Finding quadrata di un numero

Question

Ho trovato questa domanda,

scrivere una funzione che restituisce un quadrato di dato intero n senza utilizzare la moltiplicazione.

soluzione a questo è

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; 
    } 

Capisco quello che sta facendo la funzione, ma non capisco perché questo sta funzionando.

Qualcuno può spiegare perché si tratta di una soluzione funzionante?

Answer 1

Poiché la moltiplicazione viene distribuita in aggiunta. Questo probabilmente sembra misterioso, ma questa è davvero la ragione. Considerate questa moltiplicazione:

100 * 111 

Ovviamente che appena 111 spostata a sinistra da due: 11100

Questo codice sta facendo che per ogni bit che è di 1 su i, e sommando i risultati. Così si scopre per esempio 111 * 111 in

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

Splitting la moltiplicazione questo modo è consentito perché la moltiplicazione distribuisce sopra Inoltre, questo è ciò che rende 001 * 111 + 010 * 111 + 100 * 111 uguale a (001 + 010 + 100) * 111, ed ora è ovviamente uguale a 111 * 111.