[JAVA] Detailed Explanation of Intution| BIT MASKING|BIT FLIP | 5 Approach
Intution: Since we have to find the complement of a given decimal number in binary form, we will use the complement property which is N + Compliment(N) = 111...
*Intution:* Since we have to find the complement of a given decimal number in binary form, we will use the complement property which is N + Compliment(N) = 111....111.\nFoe Example : \n* N = 5 => N = 101 , Compliment(N) = 010 => 101 + 010 = 111\n* N = 8 => N = 1000 , Compliment(N) = 0111 => 1000 + 0111 = 1111\n* N = 17 => N = 10001, Compliment(N) = 01110 => 10001 + 01110 = 11111  and so on....\n\nSo we need to find out a number just greater than N having all 1 bits and then subtract N from it to get the complement.\nExample : for N=5(101) => 111 is the number just greater than 5 having all 1s. So, 111 - 101 = 010 (Compliment)\n\n***Approach1: (1ms)***\n*Explanation:* let n = 5 and i=0, j=0\n* Iteration1 : (i=0 < n) =>  i = 0 + (2^0) = 1 (1) , j = 1\n* Iteration2 : (i=1 < n) =>  i = 1 + (2^1) = 3  (11) , j = 2\n* Iteration3 : (i=3 < n) =>  i = 3 + (2^2) = 7 (111) , j = 3\n* Iteration4 : (i=7 > n) =>  loop breaks\nCompliment = i -n => 111 - 101 = 010\n```\n\nclass Solution {\n    public int bitwiseComplement(int n) {\n        \n        if(n==0) return 1;\n        \n        int i = 0;\n        int j = 0;\n        \n        while(i<n){\n            i += Math.pow(2,j);\n            j++;\n        }\n        \n        return i-n;\n    }\n}\n```\n\n\n***Approach2: (0ms)***\n*Explanation:* Just replace the arithmetical operation into bit manipulation as i += Math.pow(2^j) can be replaced with i<<n | 1.  Let n = 5 and i=0, j=0\n* Iteration1 : (i=0 < n) =>  i =0<<1 | 1 = 1 | 1 = 1\n* Iteration2 : (i=1 < n) =>  i = 1<<1 | 1 = 10 | 1 = 11 = 3\n* Iteration3 : (i=3 < n) =>  i = 3<<1 | 1 = 11<<1 | 1 = 110 | 1 = 111 = 7\n* Iteration4 : (i=7 > n) =>  loop breaks\nCompliment = i -n => 111 - 101 = 010\n\n```\nclass Solution {\n    public int bitwiseComplement(int n) {\n        \n        if(n==0) return 1;\n        \n        int i = 0;\n        \n        while(i<n){\n            i = i<<1 | 1;\n        }\n        \n        return i-n;\n    }\n}\n```\n\n\n***Approach3: (0ms)***\n*Explanation:* let n = 10 and i=1, j=0\n* Iteration1 : (i=1 < n) =>  i = 1 * 2 +1 = 3 (11)\n* Iteration2 : (i=3 < n) =>  i = 3 * 2 + 1 = 7  (111) \n* Iteration3 : (i=7 < n) =>  i = 7 * 2 + 1 = 15 (1111)\n* Iteration4 : (i=15 > n) =>  loop breaks\nCompliment = i -n => 1111 - 1010 = 0101 => 101 = 5\n\n```\nclass Solution {\n    public int bitwiseComplement(int n) {\n               \n        int i = 1;\n        \n        while(i<n){\n            i = i*2 + 1;\n        }\n        \n        return i-n;\n    }\n}\n```\n\n\n\n*In every approach at last I am calculating compliment using i - n, which can also be done using **XOR* as *i ^n  will give the compliment*:\n* i = 111 , n = 101 (5) => i ^ n = 111 ^ 101 = 010 (compliment)\n* i = 1111, n = 1010 (10) => i ^ n = 1111 ^ 1010 = 0101 (compliment)\n\n\n***Approach4: (0ms)*** : Using Xor Property\n  In complement of n , every bit is opposite to n\n* so at every place we have odd number of 1 so xor will be 1 at every place\n* n^bitwiseComplement(n) =  111....1\n\n```\nMath:\na xor b = c\n(a xor b) xor a = c xor a\n(a xor a) xor b = c xor a\n0 xor b = c xor a\nb = c xor a\n```\n\n* n^111....1 =  bitwiseComplement(n)\n* FInd the upper bound Number which has all 1\'s, Number just greater than n, will all bit 1\n```\n  Suppose N= 5\n  X = 2+1   = 3 ,   6+1   = 7 \n  X>N , X^N = 111^101 = 010\n```\n \n```\nclass Solution {\n    public int bitwiseComplement(int n) {\t     \n      int X = 1;          \n      while(X<n) X= X*2+1;\n      return X^n;        \n    }\n}\n```\n\n\n***Approach5: (0ms)***  : Using Masking\nConsider N =  10 ( 1010 )\nWe will start processing from right most bit (LSB) , Using **i** Variable we will we track bit , if it is set then we will unset it or vice-versa.\n\n```\ni=0 , intial bit position\nif  n&1  == 0  means last bit is unset , so set it \n   result += 1<<i;\nand if set then it will set to unset \n\n\t i++;// move to next bit position\n\tn >>= 1; // now move to second last bit or right shift to process next bit\n```\nfor 0 index , it is 0   bit set to 1\nfor 2 index bit , it is 0 bit set to 1\n**result =  1 + 100 =  0101**\n\n\n```\nclass Solution {\n    public int bitwiseComplement(int n) {\n        \n        if(n==0) return 1;\n        \n        int result = 0;\n        int i = 0;        \n        while(n>0){\n            if((n&1) == 0){\n                result += 1<<i;\n            }\n            i++;\n            n >>= 1;\n        }\n        \n        return result;\n    }\n}\n```\n  \n\n
['Bit Manipulation', 'Bitmask', 'Java']