# Convert Integer A to Integer B ### Source - CC150, lintcode: [(181) Convert Integer A to Integer B](http://www.lintcode.com/en/problem/convert-integer-a-to-integer-b/) ~~~ Determine the number of bits required to convert integer A to integer B Example Given n = 31, m = 14,return 2 (31)10=(11111)2 (14)10=(01110)2 ~~~ ### 題解 比較兩個數不同的比特位個數，顯然容易想到可以使用異或處理兩個整數，相同的位上為0，不同的位上為1，故接下來只需將異或后1的個數求出即可。容易想到的方法是移位后和1按位與得到最低位的結果，使用計數器記錄這一結果，直至最后操作數為0時返回最終值。這種方法需要遍歷元素的每一位，有咩有更為高效的做法呢？還記得之前做過的 [O1 Check Power of 2](http://algorithm.yuanbin.me/zh-cn/math_and_bit_manipulation/o1_check_power_of_2.html) 嗎？`x & (x - 1)`既然可以檢查2的整數次冪，那么如何才能進一步得到所有1的個數呢？——將異或得到的數分拆為若干個2的整數次冪，計算得到有多少個2的整數次冪即可。 以上的分析過程對于正數來說是毫無問題的，但問題就在于如果出現了負數如何破？不確定的時候就來個實例測測看，以-2為例，(-2) & (-2 - 1)的計算如下所示(簡單起見這里以8位為準)： ~~~ 11111110 <==> -2 -2 <==> 11111110 + & 11111111 <==> -1 -3 <==> 11111101 = = 11111101 11111100 ~~~ 細心的你也許發現了對于負數來說，其表現也是我們需要的——`x & (x - 1)`的含義即為將二進制比特位的值為1的最低位置零。逐步迭代直至最終值為0時返回。 C/C++ 和 Java 中左溢出時會直接將高位丟棄，正好方便了我們的計算，但是在 Python 中就沒這么幸運了，因為溢出時會自動轉換類型，Orz... 所以使用 Python 時需要對負數專門處理，轉換為求其補數中0的個數。 ### Python ~~~ class Solution: """ @param a, b: Two integer return: An integer """ def bitSwapRequired(self, a, b): count = 0 a_xor_b = a ^ b neg_flag = False if a_xor_b < 0: a_xor_b = abs(a_xor_b) - 1 neg_flag = True while a_xor_b > 0: count += 1 a_xor_b &= (a_xor_b - 1) # bit_wise = 32 if neg_flag: count = 32 - count return count ~~~ ### C++ ~~~ class Solution { public: /** *@param a, b: Two integer *return: An integer */ int bitSwapRequired(int a, int b) { int count = 0; int a_xor_b = a ^ b; while (a_xor_b != 0) { ++count; a_xor_b &= (a_xor_b - 1); } return count; } }; ~~~ ### Java ~~~ class Solution { /** *@param a, b: Two integer *return: An integer */ public static int bitSwapRequired(int a, int b) { int count = 0; int a_xor_b = a ^ b; while (a_xor_b != 0) { ++count; a_xor_b &= (a_xor_b - 1); } return count; } }; ~~~ ### 源碼分析 Python 中 int 溢出時會自動變為 long 類型，故處理負數時需要求補數中0的個數，間接求得原異或得到的數中1的個數。 考慮到負數的可能，C/C++, Java 中循環終止條件為`a_xor_b != 0`，而不是`a_xor_b > 0`. ### 復雜度分析 取決于異或后數中1的個數，`O(max(ones in a ^ b))`. 關于 Python 中位運算的一些坑總結在參考鏈接中。 ### Reference - [BitManipulation - Python Wiki](https://wiki.python.org/moin/BitManipulation) - [5. Expressions — Python 2.7.10rc0 documentation](https://docs.python.org/2/reference/expressions.html#shifting) - [Python之位移操作符所帶來的困惑 - 旁觀者 - 博客園](http://www.cnblogs.com/zhengyun_ustc/archive/2009/10/14/shifting.html)