[Python] O(1) solution, explained
There is very smart solution, where we spread the highest 1-bit onto all the lower bits. Try to do the following operations, see https://leetcode.com/problems/n
There is very smart solution, where we spread the highest 1-bit onto all the lower bits. Try to do the following operations, see https://leetcode.com/problems/number-of-1-bits/discuss/1044775/python-n-and-(n-1)-trick-explained for more details, idea is similar.\n\n#### Complexity\nIt is just `5` operations we need to do here.\n\n#### Code\n```python\nclass Solution(object):\n    def findComplement(self, num):\n        mask = num\n        mask |= mask >> 1\n        mask |= mask >> 2\n        mask |= mask >> 4\n        mask |= mask >> 8\n        mask |= mask >> 16\n        return num ^ mask\n```\n\n#### Remark\nAnother solutions:\n\nWe can just find length of number `k` and subtract number from `2^k-1`.\n\nWe can also use `x & (x-1)` trick, and delete ones from the end one by one until we reach power of two (we need to make step if `x & (x-1)` is not equal to zero). When we reached power of two `s`, we evaluate \n`(2s+1) ^ num`. Complexity is `O(q)`, where `q` is number of non-zero bits.\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**
['Bit Manipulation']