九章演算法 | Facebook 面試題 | 將數字轉換為十六進位

撰文 | JZ

專欄 | 九章演算法

題目描述

給出一個整型(int)的數

將其轉換為十六進位的表示方法

負數要用二進位補碼的形式表示

樣例輸入

Example 1

Input:n26nOutput:n"1a"n

Example 2

Input:n-1nOutput:n"ffffffff"n

解題思路分析

?首先，如果這個數是個正數的話，那麼非常簡單：

只需要考慮十進位數到16進位數的轉換，那麼轉換十六進位只需要用這個數對16^0,16^1,16^2……取余得到轉換成16進位後的每一位(還有一點需要注意的是16進位下10~15我們用a~f表示)。

?所以這題的關鍵就在於負數的情況。

1.負數的二進位補碼錶示

很多人都是知道：

負數在計算機內部的存儲方式是補碼的形式

負數的補碼就等於其正數反碼+1

舉個例子，如果我們使用的是4位的二進位，那麼2的表示形式就是0010，2的反碼錶示形式就是1101，所以-2的表示形式就是其反碼+1，是1110，轉換成16進位也是同樣的道理。

所以我們這種思路的做法就是16進位表示形式，然後再對其進行取反，最後再+1得到我們的答案。

2.計算機內部存儲形式轉換

一個整型的數，在計算機內部是怎麼存儲的呢？

很明顯是已二進位的形式存儲的，那麼不管我們輸入的是正數還是負數，其實計算機內部已經有了完整的存儲，那麼其實不需要我們自己再去計算反碼補碼，我們只需要對其進行2進位轉換成16進位就可以了。

因為二進位一位表示的是2,16進位一位表示的是16，那麼也就是說16進位下一位表示的是2進位下的4位(16 = 2^4)。在轉換的過程中我們就可以每四位轉換成一位，這裡有個小技巧：

用到位運算&和>>來提高運行速度，&15相當於%16

(這裡同學們可以自己思考一下為什麼這樣是一定的。)

面試官角度分析

?需要理解負數在計算機中的存儲形式，以及掌握補碼的轉換方法。

?了解計算機存儲數的機制

?不僅能轉換正數，還要能夠熟練轉換負數16進位,此題才能夠拿到hire

相關Lintcode面試題

Single-number

Single-number-ii

Single-number-iii