C++ EASY TO SOLVE || Beginner friendly with detailed explanation and dry run
Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation i.e if it\'s 101 =Complement=> 
Given a positive integer, output its **complement number**. The complement strategy is to flip the bits of its binary representation i.e if it\'s **101** =Complement=> **010**\n\n**Intuition:-**\nThere is not much of a intuition in this question as the question is loud and clear about it\'s use of bit manipulation .\n\nTo make things a bit more interesting let\'s do this question with and wihout bit manipulation \n***\n***\n**Using Bit Manipulations:-**\n***\n**Bit masking can be summarized with this image (^_^)**\n![image](https://assets.leetcode.com/users/images/d478c8d2-3fbb-49fd-956a-ae31a014a926_1640579005.4899502.jpeg) \nThus, we can conclude that masking means to keep/change/remove a desired part of information.\n***\n**Dry run of bitmasking:-**\n![image](https://assets.leetcode.com/users/images/face3402-7526-4282-becd-7564dc8b4a95_1640574890.4955626.png)\n***\n**Code[Using bitmasking]:-**\n```\nclass Solution {\npublic:\n    int bitwiseComplement(int num) {\n\t\t    //base case\n        if(num == 0) return 1;\n        unsigned mask = ~0;\n        while( mask & num ) mask = mask << 1;\n        return ~num ^ mask;\n    }\n};\n```\n**Time Complexity:** *`O(log(num))`*\n**Space Complexity:** *`O(1)`*\n***\n***\n**Using XOR**\nBasic idea is to find the smallest power of 2 that is larger than the `input number num`, and output the difference between `powerof2s` and `num` . \n\n**Dry run of XOR:-**\n```\nFor example :-\nInput: num = 5(101) ,\nThus the smallest power of 2 (and just larger than 5) is 8 (1000)\nThe output should be 8 - 5 - 1 = 2 (010).\n```\n**Code [using XOR]:-**\n```\nclass Solution {\npublic:\n    int bitwiseComplement(int num) {\n        int powerof2s = 2, temp = num;\n        \n        while(temp>>1) {\n            temp >>= 1;\n            powerof2s <<= 1;\n        }\n        \n        return powerof2s - num - 1;\n    }\n};\n```\n\n***\n***\n**Without using Bit manipulation:-**\n***\n**Algorithm:-**\n1. At start convert convert the decimal number to its binary representation \n2. Then start overriding the bits with 1 as 0 and 0 with 1 .\n3. Then again start converting the binary representation back to decimal representation .\n\n**Code:-**\n```\nclass Solution {\npublic:\n    int bitwiseComplement(int num) {\n        //base case\n        if(num==0) return 1;\n        vector<int> temp; \n\t\t// convert to binary representation\n        while( num != 0 ){\n            temp.push_back( num % 2 );\n            num /= 2;\n        } \n\t\t// make complement\n        for(int i=0; i<temp.size(); i++){\n            if( temp[i] == 1 ) temp[i] = 0;\n            else if( temp[i] == 0 ) temp[i] = 1;\n        } int res = 0;\n\t\t//Again convert them back to decimal representation \n        for(int i=temp.size()-1; i>-1; i--) res = res * 2 + temp[i];\n        return res;\n    }\n};\n```\n**An optmization of the above code:- #Credit goes to @bakar7**\n```\nclass Solution {\npublic:\n    int bitwiseComplement(int n) {\n        if (n == 0) {\n            return 1;\n        }\n\n        int answer = 0;\n        int power = 1;\n        while (n) {\n            answer += ((1 - (n % 2)) * power);\n            n /= 2;\n            power *= 2;\n        }\n\n        return answer;\n    }\n};\n```\n\n\n\n
['Bit Manipulation', 'C', 'Bitmask', 'C++']