Finding square of a number

Question

I found this question,

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

Solution to this is

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 is doing, but I don't understand why this is working.

Can anyone explain why this is a working solution?

Answer 1

Because multiplication distributes over addition. This probably sounds mysterious, but that really is the reason. Consider this multiplication:

100 * 111

Obviously that just 111 shifted left by two: 11100

This code is doing that for every bit that is 1 in i, and summing the results. So it turns for example 111 * 111 into

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

Splitting the multiplication this way is allowed because multiplication distributes over addition, that is what makes 001 * 111 + 010 * 111 + 100 * 111 equal to (001 + 010 + 100) * 111, and now it is obviously equal to 111 * 111.