Bir sayı karesi bulma

Question

Bu soruyu şu bölümde buldum:

Çarpma kullanmadan verilen bir tamsayı karesini döndüren bir işlev yazın. Buna

Çözüm

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

Ben fonksiyonu ne yaptığını anlamaya, ancak bu çalışma neden olduğunu anlamıyorum.

Bunun neden bir çalışan çözüm olduğunu açıklayan var mı?

Answer 1

çarpma daha üzerinde dağıtır çünkü. Bu muhtemelen gizemli geliyor, ama bu gerçekten sebebi. iki tarafından Açıkçası

100 * 111 

sadece 111 sola ötelenir: bu çarpma düşünün 11100

Bu kod i 1 her bit için yapma ve sonuçları toplanmasıdır. o

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

Yarma örneğin 111 * 111 için bu şekilde çarpma daha üzerinde dağıtır çünkü izin verilen çarpma döner Yani, (001 + 010 + 100) * 111 eşit 001 * 111 + 010 * 111 + 100 * 111 kılan ve şimdi açıkça 111 * 111 eşittir.