如何在沒有+

的情況下添加數字

我在面試時被問到這個問題。我沒有回答，實際上我不明白它是如何工作的。如何在沒有+

int add(int x, int y) 
{ 
    while (y != 0) 
    { 
     int carry = x & y; 
     x = x^y; 
     y = carry << 1; 
    } 
    return x; 
}

我不是問爲什麼它會產生正確的答案......首先，爲什麼算法最終會停止？對我來說並不那麼明顯。

爲了讓它停止，carry必須成爲0。有人不能簡單地解釋它嗎？

來源

2016-05-26 Alupkers

+11

這是一個[全加器]（https://en.wikipedia.org/wiki/Adder_%28electronics%29#Full_adder）。在你向左移動32次後，將會有32個零位（它是'0'）。 –

@ElliottFrisch Well ... yes））。但沒有解釋它爲什麼起作用。 – Alupkers

@Alupkers你問爲什麼算法停止？正如@ElliottFrisch所說：'curry << 1'將最右邊的位設置爲0.在最多32步（整數是Java中的32位寬）中，所有位都是0，因此'y == 0'並且循環結束。 – Nikem

line 1 : int carry = x & y; 

line 2 : x = x^y; 

line 3 : y = carry << 1;

if x = 1; y = 2;

二進制每個號碼：

0 = 00

1 = 01

2 = 10

3 = 11

線路1個代碼，

&（按位與）如果它存在於兩個操作數位的結果0二進制和操作員拷貝

x是1 => 01

y是2 => 10

結果進位是=> 00（0）

爲第2行代碼，

^（按位XOR）二進制XOR算子拷貝如果在一個操作數設置而不是兩個比特。

x爲1 => 01

y是2 => 10

結果X是=> 11（3）

用於線路3代碼，可變進位需要左移爲1位，所以現在進位是0 => 00，左移1位意味着進位現在爲0.結果y爲（0）。而while循環停止，因爲y現在是0。

x的最終結果是3.

希望這會對您有所幫助。

來源

2016-05-26 04:30:35

'x＆y'是按位而不是邏輯的。隨身攜帶在這裏仍然是0，但出於完全不同的原因而不是你所說的。 – computerfreaker

讓我們舉個例子：

x=13(1101) 
y=9(1001) 

Loop 1: 
----------------- 
y!=0 -> carry=(1101)&(1001)=1001(9) [AND Op] 
x=(1101)^(1001)=0100(4) [XOR Op] 
y=carry<<1 -> y=(carry)x2=10010(18) 

Loop 2: 
----------------- 
y!=0 -> carry=(0100)&(10010)=00000(0) 
x=(0100)^(10010)=10110(22) 
y=carry<<1 -> y=0 

loop terminated.

因此

，x是22.So中，x ^ÿ商店總和部，並且x &ÿ存儲的進位部，再進行（X & y）被移用x^y匹配數字，最後將它們XOR並存入x。 x是結果。

來源

2016-05-26 05:17:23 Hailey

如果你用布爾邏輯設計一個完整的加法器，你會得到清晰的答案 – Hailey

簡而言之，它使用y（和「carry/x & y」它變成）來修改x，直到它變成兩個整數的和。例如，

y=1 (....0001), x=anything (either .....0 or .....1) 
if x ends with 0, x&y=0 
    //x^y = x becomes ....001 (thereby adding 1) 
    //since x&y=0 the loop stops 
if x ends with 1, x&y=1 
    //x^y = x 
    //since y= x&y<<1, new y=(.....000010) 
    if x ends with 01, x&y=0 
     //x^y = x becomes ....010 (thereby adding 1) 
     //since x&y=0 the loop stops 
    if x ends with 11, x&y=1 
     //x^y = .....01 
     //since y= x&y<<1, new y=(......000100) 
     if x ends with 011 
      //stuff happens and x becomes ....100 (thereby adding 1) 
      //loop stops 
     if x ends with 111 
      //... 
      //if x ends with 111111, x becomes ....1000000 (thereby adding 1) 
      //if x ends with 1111111, x becomes ....10000000 (thereby adding 1) 
      //if x ends with 11111111, x becomes ....100000000 (thereby adding 1) 
      //well you get the idea

同樣的邏輯適用到y的所有值，並且是沒有太大從正常除了不同之處僅在於現在有2個可能的位（0和1），而不是通常10（0到9）。

來源

2016-05-26 05:58:02

回答

相關問題