天天看點

[CareerCup] 5.5 Number of Converted Bits 轉換數字所需的位數

5.5 Write a function to determine the number of bits required to convert integer A to integer B.

EXAMPLE

Input: 31,14

Output: 2

這道題給了我們兩個數字A和B,問如果将A轉化為B需要變幾個位,那麼我們很容易想到要用異或來做,因為相同位異或為0,那麼為1的為就是不相同的位,總和就是我們要求的結果。那麼此題就轉化為求異或結果中位‘1’的個數,我們可以用for循環來做,判斷異或數的最低位是否為1,若為1就計數器加1,然後将異或數向右移動一位,以此類推直至異或數為0,參見代碼如下:

解法一:

還有一種方法,這裡不是将異或數每次向右移動一位,而是用n&(n-1)來清楚最低有效位Least Significant Bit,每清除一個,計數器增1,直到異或數為0停止,參見代碼如下:

解法二: