100% Beats Solution || Using Bit Manipulation || Step by Step Explain || Easy to Understand ||
Abhiraj Pratap Singh\n\n---\n\n# UPVOTE IT....\n\n---\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \n\n- The goal of the function
# Abhiraj Pratap Singh\n\n---\n\n# UPVOTE IT....\n\n---\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n- The goal of the function is to find the bitwise complement of a given integer n. The bitwise complement of a binary number is obtained by flipping each bit (changing 0s to 1s and vice versa).\n\n---\n\n\n![Screenshot (47).png](https://assets.leetcode.com/users/images/980aa465-2f81-4215-8f1e-75176f4ca268_1705421064.7329607.png)\n\n\n---\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n1. The code initializes a variable mask to 0. This variable will be used to create a bitmask with all bits set to 1 up to the most significant bit of the given number.\n2. It also initializes a copy of the input number n as copyNum and another variable ans to store the final result.\n3. There is a check for the edge case where n is 0. If n is 0, the function returns 1 because the bitwise complement of 0 is 1.\n4. The code then enters a loop where it right shifts copyNum until it becomes 0. Meanwhile, it left shifts mask and sets the least significant bit to 1 in each iteration. This process creates a bitmask with all bits set to 1 up to the most significant bit of the original n.\n5. After constructing the bitmask, the code negates the input number n using the bitwise NOT operator (~), effectively flipping all its bits.\n6. Finally, the code applies the bitmask to the negated n using bitwise AND (&) and stores the result in ans. This step ensures that only the bits up to the most significant bit of the original n are considered in the final answer.\n\n---\n\n\n# Complexity\n\n- **Time complexity :** The time complexity of the solution is determined by the number of bits in the input number n. In the worst case, where n has k bits, the loop will run k times. Therefore, the **time complexity is O(k).**\n\n- **Space complexity:** The **space complexity is O(1)** as the algorithm uses a constant amount of extra space (for variables like mask, copyNum, and ans) that does not depend on the input size.\n\n\n---\n\n\n# Code\n```\nclass Solution {\npublic:\n    int bitwiseComplement(int n) \n    {\n        int mask=0;\n        int copyNum=n;\n        int ans=0;\n        if(n==0)\n            return 1;\n        while(copyNum!=0)\n        {\n            copyNum=copyNum>>1;\n            mask = mask <<1;\n            mask = mask  | 1;\n        }\n        n = ~n;\n        ans = mask & n;\n        return ans;\n    }\n};\n```\n\n---\n\n# if you like the solution please UPVOTE it....\n\n\n![discord-discordgifemoji.gif](https://assets.leetcode.com/users/images/c946d68a-4ab8-49e3-bc84-714ec8669136_1705420995.8539321.gif)\n\n\n---\n\n\n![fucking-die-redditor-stupid-cuck-funny-cat.gif](https://assets.leetcode.com/users/images/1bb72463-7982-4d74-abc7-fb387b285011_1705420998.7183146.gif)\n\n---\n
['Bit Manipulation', 'C++']