[Python] Fastest One Liner (timed)
Fastest Method Code\n\nclass Solution:\n    def findComplement(self, num: int) -> int:        \n        return ~num + (1<<len(bin(num))-2)\n\n\n# Analysis\nThis
# Fastest Method Code\n```\nclass Solution:\n    def findComplement(self, num: int) -> int:        \n        return ~num + (1<<len(bin(num))-2)\n```\n\n# Analysis\nThis line adds the complement of num (```~num```) with 2^n, where n = the number of bits in the binary representation of num. Let\'s take a look at why this works:\n\n## Brute Force Method\nThe straightforward method would be to convert ```num``` to a binary string, flip all the bits, and then convert that back to binary:\n```\nbinaryNum = bin(num)[2:]\nbinaryNumFlipped = \'\'\nfor i in binaryNum:\n\tbinaryNumFlipped += \'1\' if i == 0 else \'0\'\nreturn int(binaryNumFlipped, 2)\n```\n\n## Complement Method\nIn programming, the two\'s complement of a number (```~num```) is defined as ```-(num+1)```. So, the two\'s complement of 5 would be -6. The complement is with respect to 2^N\u2014that is, ```num + ~num = 2^N``` where N is the number of bits in our representation. In binary, this can be calculated by flipping all the bits and adding one. So if we convert 5 to binary, flip all the bits, and add them together, we should get 2^N-1.\n```\n  101 (5)\n+ 010 (2)\n  ---\n  111 (7)\n+   1 (1)\n  ---\n 1000 (8)\n ```\n From this, we can easily see that in order to find the complement of 5, we simply need to use the formula ```2^N - 1 - num```, where N = the number of bits in 5 (in this case, 3). In code:\n ```\n 2**(len(bin(num))-2) - 1 - num\n ```\n*Note that since Python uses the ```\'0b\'``` prefix to represent a binary number, we subtract that from the length of the binary string for 5, which Python presents as ```\'0b101\'```.*\n\n## Faster Complement with Bitshift\nWe can calculate 2^N much faster by bitshifting a 1. Since 2^N in binary is just 1 followed by N zeroes (same as in decimal, where 10^N is just 1 followed by N zeroes), we can replace 2^N with 1<<. So now we have:\n```\n(1<<(len(bin(num))-2)) - 1 - num\n```\nAnd finally, as noted before, ```~num = -(num+1)```, so we can replace this term in our code for elegance.\n```\n(1<<(len(bin(num))-2)) + ~num\n```\n\n# Time Comparison\nI used Python\'s ```timeit``` module to compare the various methods. For this test, I set it up with 500 random integers sampled from [0,100000000] and ran it 5000 times, repeating each test 5 times. Results:\n* Brute Force: **33.0518s**\n* 2^N Complement: **5.8786s**\n* Bitshift Complement: **3.7803s**\n\n*I also compared using ```~num``` vs ```-num-1```, but the results were roughly equal.*\n\n\n
['Bit Manipulation', 'Python', 'Python3']