最新消息:热烈庆祝IT小记上线!

[置顶] Add, Subtract, Multiply numbers without using "+", "-", "*" operation

Approach the problem using bit manipulation.


Add Number is the base operation for Subtract and Multiply.

In binary representation, when adding two numbers, we can separate sum and carry procedure.


For the Sum: If two bit are both 0 or both 1, the consequence is 0. If one of them is 0, another is 1, the consequence is 1. So, it is XOR operation in bit manipulation.

For the Carry: If both previous bit of two number are 1, then carry will be 1 for the current bit. So, it is an AND operation followed by left shift 1.


Subtract: Based on Two's Complement

Reference : http://en.wikipedia.org/wiki/Two's_complement 


Multiply: Using Ethiopian Multiplication 

Reference : http://rosettacode.org/wiki/Ethiopian_multiplication


Code is listed below:

public class OperationNum {
	public static int add(int a, int b){
		if (b==0) return a;
		int sum = a^b;
		int carry = (a & b)<<1;
		return add(sum,carry);
	}
	
	public static int negative (int x) {
		return add(~x,1);
	}
	
	public static int subtract(int x, int y){
		return add(x, negative(y));
	}
	
	public static boolean isEven (int x) {
		return (x & 1) == 0;
	}
	
	public static int multiply (int x, int y){
		if (x<0 && y<0){
			return multiply(negative(x),negative(y));
		}
		if (x<0 && y>=0){
			return multiply(y,x);
		}
		int ret = 0;
		while (x>0) {
			if (!isEven(x)){
				ret = add(ret,y);
			}
			x>>=1;
			y<<=1;
		}
		return ret;
	}
	
	public static void main(String[] args){
		int ret = OperationNum.add(-3,5);
		System.out.println(" -3 + 5    ---->" + ret);
		ret = OperationNum.subtract(0,-1);
		System.out.println(" 0 - (-1)  ---->" + ret);
		ret = OperationNum.subtract(0,5);
		System.out.println(" 0 - 5     ---->" + ret);
		ret = OperationNum.multiply(0,0);
		System.out.println(" 0 * 0     ---->" + ret);
		ret = OperationNum.multiply(0,-32);
		System.out.println(" 0 * (-32) ---->" + ret);
		ret = OperationNum.multiply(8,0);
		System.out.println(" 8 * 0     ---->" + ret);
		ret = OperationNum.multiply(-7,-3);
		System.out.println(" -7 * (-3) ---->" + ret);
		ret = OperationNum.multiply(-7,2);
		System.out.println(" -7 * 2    ---->" + ret);
	}
}


leetcode 刷刷刷 下一篇

猜您喜欢

备案号:苏ICP备12016861号-4