Java 1 line bit manipulation solution
I post solution first and then give out explanation. Please think why does it work before read my explanation.\n\n\npublic class Solution {\n    public int find
I post solution first and then give out explanation. Please think why does it work before read my explanation.\n\n```\npublic class Solution {\n    public int findComplement(int num) {\n        return ~num & ((Integer.highestOneBit(num) << 1) - 1);\n    }\n}\n```\n\nAccording to the problem, the result is\n1. The ```flipped``` version of the original ```input``` but\n2. Only flip ```N``` bits within the range from ```LEFTMOST``` bit of ```1``` to ```RIGHTMOST```. \nFor example input = ```5``` (the binary representation is ```101```), the ```LEFTMOST``` bit of ```1``` is the third one from ```RIGHTMOST``` (```100```, ```N``` =  3). Then we need to flip 3 bits from ```RIGHTMOST``` and the answer is ```010```\n\nTo achieve above algorithm, we need to do 3 steps:\n1. Create a bit mask which has ```N``` bits of ```1``` from ```RIGHTMOST```. In above example, the mask is ```111```. And we can use the decent Java built-in function ```Integer.highestOneBit``` to get the ```LEFTMOST``` bit of ```1```, left shift one, and then minus one. Please remember this wonderful trick to create bit masks with ```N``` ones at ```RIGHTMOST```, you will be able to use it later.\n2. Negate the whole input number.\n3. ```Bit AND``` numbers in step ```1``` and ```2```.\n\nThree line solution if you think one line solution is too confusing:\n```\npublic class Solution {\n    public int findComplement(int num) {\n        int mask = (Integer.highestOneBit(num) << 1) - 1;\n        num = ~num;\n        return num & mask;\n    }\n}\n```\n\n```UPDATE```\nAs several people pointed out, we don't need to left shift 1. That's true because the highest ```1``` bit will always become ```0``` in the ```Complement``` result. So we don't need to take care of that bit.\n\n```\npublic class Solution {\n    public int findComplement(int num) {\n        return ~num & (Integer.highestOneBit(num) - 1);\n    }\n}\n```
[]