軟體面試問題(一)

最近都在準備一些公司的預聘面試，但老實說準備的還不夠充分，所以常常被面試官電在牆上，然後電完後在被拖出來繼續電。

身為一個從小看獵人的人，也希望自己像奇犽一樣，被電久了之後也可以學會特殊的能力(?)

所以還是決定每次被電後去面對問題，把不會或不清楚的地方的搞懂。所以這篇就會分享幾題當初被問到的問題，以及事後做完功課後自己會怎麼去回答。其實有想過把所有被問過的題目整理起來變成一篇分享，不過目前沒有那個時間，所以會先以一篇一篇的形式，每篇紀錄一些內容這樣。

logical operator 和 bitwise operator的差別?

這題一開始我有簡單的回答出來，當時我的回答是這樣的：

• bitwise operator如|、&會以bit的角度去看兩側的operand，針對每一個bit去做運算
• 而logical operator如||、&&則是以boolean的角度去看兩側的operand，在C語言中，只要不是0的值會被視為true，0則會被視為false。基於此概念下去做運算

不過顯然這樣的回答還不夠充分，後來面試官問說除此之外還有什麼差異我就回答不出了，回來想了一下後想針對原本的回答再進一步補充：

使用bitwise operator和logical operator的差異在於，今天如果有個敘述”if( 4 __ 2) {…}”，考慮使用 && 和 & 的運算就會得到不一樣的結果

• 4 && 2 的時候由於兩個數都不為0，所以會變成true && true = true
• 4 & 2 的時候會以bit的角度去看，也就是(0100) & (0010) = 0，所以答案會是false

此外，logical operator還具有另一個特性，也就是short-circuit evaluation，在某些情況下他不會去看後面的條件：

• 對於&&來說，如果前面的條件是false，則不管後面條件是什麼結果都會是false，此時就不會去看後面的條件了
• 同理，對於||來說，如果前面是true則不會去看後面的條件

這樣會造成什麼結果呢? 考慮以下程式碼：

1

while( j > 0  && arr[j-1] >= 0 ){ ... }

1

while( arr[j-1] >= 0 && j > 0){ ... }

後者的程式碼可能會有問題，例如今天當j = 0時，while的第一個判斷就會出現問題了(arr[-1])，而如果先判斷j>0這個條件的話，因為short-circuit的特性他並不會去判斷第二個條件，此時就不會取到負的index。

給予兩個bit sequence (s1, s2)，請把s1的 1~3個bit (從第0個bit開始計算)指定給s2

這題後來回去就想出來了，可是當下腦袋就是打結怎麼想就差一點點..

假設一下s1 s2會比較好去思考，由於是白板題，所以我覺得一邊寫一邊把思考過程講給對方聽還不錯，假設：s1: 10101, s2: 11000

下面提供兩個後來想到的解法，但是我沒有實際去測試過，如果有錯誤還請提出~

[A1]

要取得s1的1~3bit相對簡單，只要把對應的位置與1做&，其他位置與0做&即可，也就是s1&14(二進位的01110)

接下來就要把s2的0~3bit變成0，然後加上s1的1~3bit和s2的第0個bit，也就是：

1

s2 = ((s2 >> 4) << 4) + (s1 & 14) + (s2 & 1)

• ((s2 >> 4) << 4)先把值向右shift 4個bit在向左shift回來，會把那些部分都變成0
• (s1 & 14)是s1的1~3bit
• (s2 & 1)是s2的第0個bit，由於剛剛shift的時候被清空了，所以這裡要加回來

[A2]

和[A1]類似的想法，都是先把s2的1~3bit變成0

1. 先取得s1的1~3bit: s1 & 14

2. 把s2的1~3bit清空，這裡想到了另一種方式，也就是s2 & (1111…10001) = s2 & ~(000…01110) = s2 & ~14

3. 這邊用到了XOR的特性，XOR 0會是原本的數值

• (s1 & 14)除了1~3bit以外的值都是0，所以對s2 XOR後1~3bit都會是s2原本的數值
• s2的1~3bit都是0，所以與(s1 & 14)XOR之後的1~3bit都會是s1原本的數值

所以[A2]的過程總共是:

1
2
3
4
5

int mask = s1 & 14;
 
s2 = s2 & (~14);
 
s2 = s2 ^ mask;

• ← Newer Post
• Older Post →