不使用加减乘除将一个数扩大n倍

Love The Way You Lie 2021-10-30 00:48 134阅读 0赞

### 思路 ###

计算机语言中除了加减乘除运算之外，还有移位，异或，模运算这些位运算操作。不能使用加减乘除那肯定是用位运算操作实现了。

考虑计算机的加法运算，学过数字电路的应该知道加法器，下图是一个半加器电路：  
![在这里插入图片描述][20190820124427764.png]

*  S = A xor B
 *  C = A and B

其真值表如下：  
![在这里插入图片描述][20190820124908245.png]  
半加器计算 `1+1`时  
S = 1 xor 1 = 0  
C = 1 and 1 = 1  
进位C为1，所谓进位就是比S高一位， 所以最后结果是C左移一位之后与S异或得到最终结果，也就是10。

*  考虑如下例子：  
    5 + 7

<table> 
 <thead> 
  <tr> 
   <th>num</th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th>reult</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>1</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>0</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>7</td> 
  </tr> 
  <tr> 
   <td>n = 5 ^ 7(原来位的运算结果)</td> 
   <td>0</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>m = (5 &amp; 7) &lt;&lt; 1(进位)</td> 
   <td>1</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>10</td> 
  </tr> 
  <tr> 
   <td>n = n ^ m</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>8</td> 
  </tr> 
  <tr> 
   <td>m = (n &amp; m) &lt;&lt; 1</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>n = n ^ m</td> 
   <td>1</td> 
   <td>1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>12</td> 
  </tr> 
  <tr> 
   <td>m = (n &amp; m) &lt;&lt; 1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

当最后判断进位，m为0时,此时运算结束，得到最后结果。

### C语言程序实现 ###

#include<stdio.h>
    
    // calculate num1 + num2 
    int add(int num1, int num2)
    { 
    	int sum, carry, result;
    	sum = carry = 0;
    	do
    	{ 
    		sum = num1 ^ num2;
    		carry = (num1 & num2) << 1;
    		num1 = sum;
    		num2 = carry;
    	}while (carry != 0)
    	return sum;
    }
    
    int mul(int num1, int num2)
    { 
    }
    	
    
    int main()
    { 
    	
    }

[20190820124427764.png]: /images/20211029/3f27340a173d4b5ebf3340428795ed5c.png
[20190820124908245.png]: /images/20211029/d2985c96f62549e2ac8e15cfff470622.png