## Apple Interview Question

Developer Program Engineers<pre lang="java" line="1" title="CodeMonkey28074" class="run-this">public class BitwiseSquare {

/**

* Simple multiplication using bitwise operators.

*/

public static int multiply(int a, int b) {

int product = 0;

while (a > 0) {

if ((a & 1) != 0)

product += b;

b = b << 1;

a = a >> 1;

}

return product;

}

/**

* This is better explained using an example. Example: 24 = 16+8 (bit 4th

* and 3rd) 24^2 = (16+8)^2 = 16^2 + 8^2 + 2x16x8 26^2 = (16+8+2)^2, using

* powers of 2. (16+8+2)^2 = 2*2+2 + 8*8+2*8*(2) + 16*16+2*16*(2+8) = 676

*/

public static int square(int a) {

int bitpos = 0;

int result0 = 0; // 16*16 + 8*8 + 2*2

int result1 = 0; // 2 + 2*8*(2) + 2x16x(2+8)

int temp = 0; // 2+8+16

while (a > 0) {

if ((a & 1) != 0) {

// 16^2 = (2^4)^2 = 2^(4+4)

int b = 1;

// b = 16 = 2^4

b = b << bitpos;

// result1 += 2 * b * temp;

result1 += multiply(b, temp) << 1;

temp += b;

// b = 16^2 = 2^(4+4)

b = b << bitpos;

result0 += b;

}

a = a >> 1;

bitpos++;

}

return result0 + result1;

}

public static void main(String[] args) throws java.lang.Exception {

for (String s : args) {

int val = Integer.parseInt(s);

System.out.println(val + "^2 = " + square(val));

}

}

}

</pre><pre title="CodeMonkey28074" input="yes">1 3 26</pre>

why not just call your multiply () with both a & b same i.e multiplication of a & b where a=b?

another solution:

Use the fact that (n-1)^2 = n^2 -2n + 1 and use recursion

```
{
int square(int n)
{
if(n == 1 || n == 0) return n;
if(n < 0) return square(-n);
return square(n-1)+n+(n-1);
}
```

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace ConsoleApplication1

{

class Program

{

static void Main(string[] args)

{

int result;

result = sqrtnum(100);

Console.WriteLine("The value is " + result);

Console.Read();

}

public static int sqrtnum(int num)

{

int total = 0;

int count = num;

List<int> l = new List<int>();

for (int i = -1; i < count; i++)

{

l.Add(num);

Console.WriteLine(l.ToString());

}

for (int j = 0; j < l.Count - 1; j++)

total += l[j];

return total ;

}

}

}

A lot of answers are focusing on integer numbers only. I don't think it states anywhere that we should limit the function to integer numbers.

if we're allowed to use <math.h> you can do:

```
double square(double x) {
return exp(log(x) + log(x));
}
```

a^b = exp(b*log(a))

- thomas November 23, 2010