Search squared numbers

Question

I found this question,

write a function that returns the square of a given integer n without using multiplication.

Solution to this

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

I understand what the function does, but I do not understand why this works.

Can someone explain why this is a working solution?

Answer 1

Since multiplication extends over additions. It may sound mysterious, but actually it is the reason. Consider this multiplication:

 100 * 111 

Obviously, only 111 is shifted to the left by two: 11100

This code does this for every bit that is 1 in i , and summing up the results. Thus, it turns, for example, 111 * 111 into

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

Splitting the multiplication in this way is allowed, because the multiplication is distributed by adding, which makes 001 * 111 + 010 * 111 + 100 * 111 equal to (001 + 010 + 100) * 111 , and now it is obviously equal to 111 * 111 .