Python O( lg n ) XOR masking. [ w' explanation ] 有中文解析專欄
Python O( log n ) sol. based on XOR masking. \n\n\u4E2D\u6587\u89E3\u6790\u5C08\u6B04\n\n---\n\nExample explanation\n\n---\nExample_#1\n\ninput: 5\n\n5 = 0b 101
Python O( log n ) sol. based on XOR masking. \n\n[\u4E2D\u6587\u89E3\u6790\u5C08\u6B04](https://vocus.cc/article/66c6eddefd89780001e679b8)\n\n---\n\nExample explanation\n\n---\nExample_#1\n\ninput: **5**\n\n5 = 0b **101**\n**bits length** of 5 = **3**\n**masking** = **2^3 -1** = 8 - 1 = **7** = 0b **111**\n\n5 = 0b **101**\n7 = 0b **111** ( **XOR** )\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n**2** = 0b **010**\n\noutput: **2**\n\n---\nExample_#2\n\ninput: **9**\n\n9 = 0b **1001**\n**bits length** of 9 = **4**\n**masking** = **2^4 -1** = 16 - 1 = **15** = 0b **1111**\n\n09 = 0b **1001**\n15 = 0b **1111** ( **XOR** )\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\n**06** = 0b **0110**\n\noutput: **6**\n\n---\n**Implementation** with bit length calculation:\n```\nfrom math import floor\nfrom math import log\n\nclass Solution:\n    def findComplement(self, num: int) -> int:\n        \n        bits_length = floor( log(num, 2) + 1)\n        \n        return num^( 2**bits_length - 1 )\n```\n\n---\n\n**Implementation** with python built-in method, **[.bit_length()](https://docs.python.org/3/library/stdtypes.html#int.bit_length)**,of integer:\n\n```\nclass Solution:\n    def findComplement(self, num: int) -> int:\n        \n        bit_mask = 2**num.bit_length() -1 \n        \n        return ( num ^ bit_mask )\n```\n\n---\n\nRelated leetcode challenge:\n\n[Leetcode #1009 Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/)
['Bit Manipulation', 'Bitmask', 'Python', 'Python3']