Beat 100% -> 0ms | C++ | T.C. -> O(logn) | S.C. -> O(1)
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the complement of a given integer num, where the complemen
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the complement of a given integer num, where the complement is obtained by flipping all bits in the binary representation of num (i.e., converting 1s to 0s and 0s to 1s). The integer num will have no leading zeros.\n\n---\n\n\n---\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Understanding the Binary Representation:**\n\n- The binary representation of num is a sequence of 1s and 0s.\nFor example, num = 5 has a binary representation 101.\n\n---\n\n\n2. **Finding the Highest Bit Set:**\n\n- The goal is to create a mask that has the same length as the binary representation of num but with all bits set to 1. This mask will help in flipping all bits of num.\n\n- The log2(num) function calculates the position of the highest bit set in num.\n\n- Shifting 1 left by the result of log2(num) gives us a number with only the highest bit set.\n\n- For num = 5 (binary 101), log2(5) returns 2, and 1 << 2 results in 100 (which is 4 in decimal).\n\n---\n\n\n3. **Creating the Mask:**\n\n- The next step is to create a mask where all bits are set to 1 up to the highest bit of num.\n\n- By doubling the result (multiplying by 2) and subtracting 1, we get a mask with all bits set to 1 in the positions that num occupies.\n\n- Continuing with num = 5 (binary 101), doubling 100 gives 1000 (binary for 8), and subtracting 1 gives 0111 (binary 7).\n\n---\n\n\n4. **Flipping the Bits:**\n\n- Finally, to get the complement of num, we XOR num with the mask. XORing with 1 flips the bit, and XORing with 0 keeps it the same.\nFor num = 5 (binary 101), XOR with 0111 results in 010, which is the binary for 2.\n\n---\n\n---\n\n\n\n# Complexity\n- Time complexity: O(logn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n---\n\n---\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int findComplement(int n) {\n        unsigned int highestBit = 1 << (int)(log2(n));\n        unsigned int mask = (highestBit * 2) - 1;\n        return n ^ mask;\n    }\n};\n\n```\n![e78e83d2-3828-4681-96d5-40e225e1d8b0_1699854685.5280945.jpeg](https://assets.leetcode.com/users/images/0936cd0d-d78d-4344-b022-47a97e9e314a_1724286072.7974572.jpeg)\n
['C++']