clz finds bit length then xor->1 line||0ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \ncount how many bits the number num needs by using clz or countl_zero(since C++20)\nThen
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\ncount how many bits the number num needs by using clz or countl_zero(since C++20)\nThen xor with 0x7fffffff then & (1<<bitLen)-1 if bitLen<31\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Count bLen by using `bLen=(31-countl_zero((unsigned)num))` or system bultin `__builtin_clz`. They have the same effect like `int(log2(num))`.\n2. Compute the mask=(1<<bitLen)-1 if bitLen<31\n3. the answer is `(INT_MAX^num)&mask=(~num)&mask`.\n4. 1-liner C++ is given which is simpler; Python 1-liner is done in the similar way.\n5. For avoiding of overflow, take `1u` in 1-liner without if-branch\n6. For better understanding, add a solution using iterations with slight bit manipulations. \n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(\\max(\\log_2(n),32))$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n# Code\n```cpp []|| C++ 0ms beats 100%\nclass Solution {\npublic:\n    int findComplement(int num) {\n        int bLen=(31-__builtin_clz(num));\n        int mask=(bLen==31)?INT_MAX:((1<<bLen)-1);\n        return (INT_MAX^num)&mask;\n    }\n};\n```\n# C++/Python 1-liner using bit_length()\nFor avoiding of overflow in C++, take `1u` in 1-liner\n```C++ []\nclass Solution {\npublic:\n    static int findComplement(int num) {\n        return num^((1u<<(32-countl_zero((unsigned)num)))-1);\n    }\n};\n```\n```Python []\nclass Solution:\n    def findComplement(self, num: int) -> int:\n        return num^((1<<num.bit_length())-1)\n        \n```\n# C++ loop with bit manipulation\n```\nclass Solution {\npublic:\n    static int findComplement(int num) {\n        if (num==1) return 0;\n        int ans=0;\n        for(int b=0; num; b++, num>>=1){// num/=2\n            ans+=(1-(num&1))<<b;// (num%2==0?1:0)*(1<<b)\n        }\n        return ans;\n    }\n};\n```
['Bit Manipulation', 'Bitmask', 'C++', 'Python3']