Java | Fastest and easiest ever | Linear T & S | Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nWe have to flip the bits, i.e. we have to find compliment, thus I think ~n is a really 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe have to flip the bits, i.e. we have to find compliment, thus I think ~n is a really good option, but we have a problem over here, it flips all the bits  that is if an integer only takes 7 bits and rest in front are zeros, it will flip them too which is not required! Thus let\'s find the number of bits in which a number can fit in, suppose we have 20 only, it\'s binary representation is 10100 and  by this formula: \n\n##### nBits = (Math.log(num) / Math.log(2)) + 1\n\nWe can get the number of bits in which our number will definitely fit in, thus now let\'s prevent our prefix zeros to flip, thus create a mask \n\n##### mask = (1 << nBits) - 1;\n\nThis will make sure all prefix zeros are preserved, thus let\'s save our zeros now! I hope & will work as it will make 1-0 = 0 and 1-1 = 0, thus & our ~num with our mask\n\n##### ans = ~num & mask\n\nHERE WE GO! LINEAR TIME AND SPACE!\n\n# Complexity\n- Time complexity: O(1)\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# Code\n```\nclass Solution {\n    public int findComplement(int num) {\n        int nBits = (int)Math.floor((Math.log(num) / Math.log(2)) + 1);\n        int mask = (1 << nBits) - 1;\n        return ~num & mask;\n    }\n}\n```
['Math', 'Bit Manipulation', 'Java']