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