Addition, Subtraction, Multiplication using bit operators

The key for addition is to think about how numbers the carry works. You want to get the sum without worrying about caring, and then sum first (XOR), and then worry about the carry bit (AND << 1).

// Iterative
public static int add(int a, int b) {
int sum = a^b; // add without carrying
int carry = (a&b) << 1; // carry, but don't add
int temp = sum;
while(carry!= 0) {
sum = temp ^ carry;
carry = (temp&carry) << 1;
temp = sum;
}

return sum;
}

public static int add_r(int a, int b) {
if (b == 0)
return a;
int sum = a^b; // add without carrying
int carry = (a&b) << 1; // carry, but don't add
return add_r(sum,carry);

}
/*
In 2's complement representation, subtraction is performed by adding the additive inverse of a number. A number is negated by forming the complement and adding 1.
*/
public static int subtract(int a, int b) {
return add(a, add(~b,1));
}

static int multiply(int x, int y) {
int res = 0;

if (x<0 && y=0 && y0) {
if ((y&1) == 0) { // is even?
x = x <> 1;
} else {
res = add_r(res,x);
y=add_r(y,-1);
}
}
return res;
}

Advertisements
This entry was posted in Java and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s