位运算_加减乘除

计算机最基本的操作单元是字节(byte)，一个字节由8个位(bit)组成，一个位只能存储一个0或1，其实也就是高低电平。无论多么复杂的逻辑、庞大的数据、酷炫的界面，最终体现在计算机最底层都只是对0101的存储和运算.

1. 加法运算

加法运算：将一个整数用二进制表示，其加法运算就是：相异（^）时，本位为1，进位为0；同为1时本位为0，进位为1；同为0时，本位进位均为0.
所以，不计进位的和为sum = a^b，进位就是arr = a&b,(与sum相加时先左移一位，因为这是进位）。

/*
 *思路:
 *    先不计进位相加，然后再与进位相加，随着递归，进位会变为0，递归结束。 
*/
function add($a, $b) {
	if ($b == 0) {
		return $a;
	}
	$s = $a ^ $b; //没有进位的加法运算
	$c = ($a & $b) << 1; //进位并且左移运算
	return add($s, $c); //进行递归，相加
}

2. 减法运算

减法运算：a-b = a+(-b) 根据补码的特性，各位取反加1即可（注意得到的是相反数，不是该数的补码，因为符号位改变了）

//首先取减数的补码，然后相加
function substract($a, $b) {
	return add($a, negtive($b));
}
//取补码
function negtive($b) {
	return ~$b + 1;
}

3. 乘法运算

乘法运算：将b个a相加。

function multiply($a, $b) {
	//取绝对值
	$multiplicand = $a < 0 ? add(~$a, 1) : $a;
	$multiplier = $b < 0 ? add(~$b, 1) : $b;

	//计算绝对值的乘积
	$product = 0;
	$count = 0;
	while ($count < $multiplier) {
		$product = add($product, $multiplicand);
		$count = add($count, 1);
	}
	//确定乘积的符号
	if (($a ^ $b) < 0) {
		$product = add(~$product, 1);
	}
	return $product;
}

function multiply($a, $b) {
	$multiplicand = $a < 0 ? add(~$a, 1) : $a;
	$multiplier = $b < 0 ? add(~$b, 1) : $b;
	$product = 0;

	while($multiplier > 0) {
		if (($multiplier & 0x1) > 0) {
			$product = add($product, $multiplicand);
		}
		$multiplicand = $multiplicand << 1;
		$multiplier = $multiplier >> 1;

	}
	if (($a ^ $b) < 0) {
		$product = add(~$product, 1);
	}
	return $product;
}

function multiply($a, $b) {
//	$res = -1;
	if ($a < $b) {
		return 0;
	} else {
		$res = sub(substract($a, $b), $b) + 1;
	}
	return $res;
}

4. 除法运算

除法运算：计算a最多能减去多少个b。

function divide($a, $b) {
    // 先取被除数和除数的绝对值
    $dividend = $a > 0 ? $a : add(~$a, 1);
    $divisor = $b > 0 ? $a : add(~$b, 1);

    $quotient = 0;// 商
    $remainder = 0;// 余数
    // 不断用除数去减被除数，直到被除数小于被除数（即除不尽了）
    while ($dividend >= $divisor) {// 直到商小于被除数
        $quotient = add($quotient, 1);
        $dividend = substract($dividend, $divisor);
    }
    // 确定商的符号
    if (($a ^ $b) < 0) {// 如果除数和被除数异号，则商为负数
        $quotient = add(~$quotient, 1);
    }
    // 确定余数符号
    $remainder = $b > 0 ? $dividend : add(~$dividend, 1);
    return $quotient;// 返回商
}

补充：
计算机系统中，数值一律用补码来表示：因为补码可以使符号位和数值位统一处理，同时可以使减法按照加法来处理。

补码简单介绍：数值编码分为原码，反码，补码，符号位均为0正1负。

• 原码 -> 补码：数值位取反加1
• 补码 -> 原码：对该补码的数值位继续 取反加1
• 补码 的绝对值（称为真值）：正数的真值就是本身，负数的真值是各位（包括符号位）取反加1（即变成原码并把符号位取反）
• b -> -b ：各位（包括符号位）取反加1