Python | Bit Manipulation
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution(object):\n    def findComplement(self, num):\n        \n        compliment = 1\n 
[see the Successfully Accepted Submission](https://leetcode.com/problems/number-complement/submissions/943115373/?envType=daily-question&envId=2024-08-22)\n\n# Code\n```python3 []\nclass Solution(object):\n    def findComplement(self, num):\n        \n        compliment = 1\n        while compliment <= num:\n            compliment = compliment << 1\n        \n        leftCompliment=compliment - 1\n        compliment=(leftCompliment) ^ num\n        \n        return compliment\n        \n```\n\n# Step-by-Step Breakdown\n\n### Initialization:\n- A variable `compliment` is initialized to `1`. This variable is used to find a mask that can cover all the bits of `num`.\n\n### Calculate the Bit Mask:\n- The `while` loop runs until `compliment` is greater than `num`. In each iteration, `compliment` is left-shifted by 1 position (`compliment = compliment << 1`), effectively doubling its value. This continues until `compliment` exceeds `num`. The purpose of this loop is to determine a mask that has all bits set to `1` up to the leftmost bit of `num`.\n\n### Mask Calculation:\n- After the loop, `compliment` will be a power of 2 that is just greater than `num`. The mask, `leftCompliment`, is then calculated as `compliment - 1`. This mask will have all bits set to `1` up to the same bit length as `num`.\n\n### Compute the Complement:\n- The complement of `num` is calculated by performing a bitwise XOR between `leftCompliment` and `num`. The XOR operation flips the bits of `num` where the mask has bits set to `1`.\n\n### Return the Complement:\n- Finally, the method returns the computed complement.\n\n## Example\n\nLet\u2019s consider an example to illustrate how this works:\n\n- Suppose `num = 5`, which in binary is `101`.\n- The `compliment` variable will progress as follows:\n  - Initially: `compliment = 1` (binary `001`)\n  - After first shift: `compliment = 2` (binary `010`)\n  - After second shift: `compliment = 4` (binary `100`)\n  - After third shift: `compliment = 8` (binary `1000`, greater than `101`)\n- The `leftCompliment` mask is `8 - 1 = 7` (binary `111`).\n- The XOR operation: `7 ^ 5 = 2` (binary `010`).\n\nThus, the method returns `2`, which is the bitwise complement of `5`.\n\n## Complexity\n\n- **Time Complexity**: `O(n)`, where `n` is the number of bits in `num`.\n- **Space Complexity**: `O(1)`, as we use a constant amount of space.\n\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']