中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

用位運算實現兩個整數的加減乘除(根據網上內容整理)

發布時間:2020-07-29 01:33:00 來源:網絡 閱讀:1531 作者:cjs520 欄目:編程語言

一、整數加法

用位運算實現加法也就是計算機用二進制進行運算,32位的CPU只能表示32位內的數,這里先用1位數的加法來進行,在不考慮進位的基礎上,如下

  1. 1 + 1 = 0

  2. 1 + 0 = 1

  3. 0 + 1 = 1

  4. 0 + 0 = 0

很明顯這幾個表達式可以用位運算的“^”(按位異或)來代替,如下

  1. 1 ^ 1 = 0

  2. 1 ^ 0 = 1

  3. 0 ^ 1 = 1

  4. 0 ^ 0 = 0

要獲取進位我們可以如下思考:

  1. 0 + 0 = 0

  2. 1 + 0 = 0

  3. 0 + 1 = 0

  4. 1 + 1 = 1

  5. //換個角度看就是這樣

  6. 0 & 0 = 不進位

  7. 1 & 0 = 不進位

  8. 0 & 1 = 不進位

  9. 1 & 1 = 進位

正好,在位運算中,我們用“<<”表示向左移動一位,也就是“進位”。那么我們就可以得到如下的表達式://進位可以用如下表示:(x&y)<<1


到這里,我們基本上擁有了這樣兩個表達式

  1. x^y //執行加法

  2. (x&y)<<1 //進位操作

我們來做個2位數的加法,在不考慮進位的情況下

  1. 11+01 = 100  // 本來的算法

  2.  

  3. // 用推算的表達式計算

  4. 11 ^ 01 = 10

  5. (11 & 01) << 1 = 10

  6.  

  7. //到這里 我們用普通的加法去運算這兩個數的時候就可以得到 10 + 10 = 100

  8. //但是我們不需要加法,所以要想別的方法,如果讓兩個數再按剛才的算法計算一次呢

  9. 10 ^ 10 = 00

  10. (10 & 10) << 1 = 100

到這里基本上就得出結論了,其實后面的那個 “00” 已經不用再去計算了,因為第一個表達式就已經算出了結果。

繼續推理可以得出三位數的加法只需重復的計算三次得到第一個表達式的值就是計算出來的結果。

現總結如下:
定理1:設a,b為兩個二進制數,則a+b = a^b + (a&b)<<1。
證明:a^b是不考慮進位時加法結果。當二進制位同時為1時,才有進位,因此 (a&b)<<1是進位產生的值,稱為進位補償。將兩者相加便是完整加法結果。
定理2:使用定理1可以實現只用位運算進行加法運算。
證明:利用定理1中的等式不停對自身進行迭代。每迭代一次,進位補償右邊就多一位0,因此最多需要加數二進制位長度次迭代,進位補償就變為0,這時運算結束。

加法的C代碼如下:

int add(int a, int b)
{
   if (b == 0)
       return a;

   int sum = a ^ b;
   int carry = (a & b) << 1;

   return add(sum, carry);
}

二、整數減法

減法只是將減數取補碼(按位取反,加1),然后相加。

減法的C代碼如下:

int sub(int a, int b)
{
   return add(a, add(~b, 1));
}

三、整數乘法

乘法就是將乘數寫成(2^0)*k0 + (2^1)*k1 + (2 ^2)*k2 + ... + (2^31)*k31,其中ki為0或1,然后利用位運算和加法就可以了。

乘法的C代碼如下:

int mul(int a, int b)
{
   int res = 0;
   for (int i = 1; i; i <<= 1, a <<= 1)
      if (b & i)
          res = add(res, a);

   return res;
}

四、整數除法

除法就是由乘法的過程逆推,依次減掉(如果夠減的話)divisor << 31、divisor << 30、... 、divisor << 2、divisor << 1、divisor(要保證不能溢出)減掉相應數量的除數就在結果加上相應的數量。

除法的C代碼如下:

int div(int a, int b)
{
   int sign = 1;
   if (a & (1 << 31))
   {
       a = ~sub(a, 1);
       sign ^= 1;
   }
   if (b & (1 << 31))
   {
       b = ~sub(b, 1);
       sign ^= 1;
   }

   int res = 0;
   for (int i = 0x8000; i; i >>= 1)
       if ((a >> i & 0xFFFF) >= b)
       {
           res = add(res, 1 << i & 0xFFFF);
           a = sub(a, b << i & 0xFFFF);
       }

   if (!sign)
       res = ~sub(res, 1);

   return res;
}


向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

大厂| 贵定县| 天等县| 太保市| 贵德县| 洛南县| 射洪县| 修水县| 金秀| 内乡县| 乐亭县| 工布江达县| 淮滨县| 涿州市| 潮州市| 黄石市| 尉犁县| 安徽省| 邹城市| 苗栗市| 车致| 英超| 灵台县| 天津市| 定西市| 应用必备| 晋中市| 伊金霍洛旗| 繁昌县| 达拉特旗| 教育| 云安县| 西藏| 永顺县| 阜康市| 汝城县| 河西区| 怀宁县| 玛曲县| 海伦市| 全南县|