4 approaches: bitwise operation, math formular, one naive simulation, and bonus
Find the smallest binary number c that is all 1s, (e.g. \u201C111\u201D, \u201C11111\u201D) that is greater or equal to N.\nans = C ^ N or C \u2013 N\n\nMore de
Find the smallest binary number c that is all 1s, (e.g. \u201C111\u201D, \u201C11111\u201D) that is greater or equal to N.\nans = C ^ N or C \u2013 N\n\nMore details:\n^: bitwise XOR operator\n**Table 1. The truth table of bitwise XOR operator:**\n**1^0 = 1\n1^1 = 0**\n0^0 = 0\n0^1 = 1\n**The upper two rows  of Table 1 is used in the problem.**\n\n\n\nTime complexity: O(log(n))\nSpace complexity: O(1)\n\nSolution 1:  bit shift based solution\n```\nclass Solution {// bit shift based solution\npublic:\n  int bitwiseComplement(int N) {\n    int c = 1; // c = pow(2, x) \u2013 1; c is the smallest number >= N\n    while (c < N) \n      c = (c << 1) | 1;\n      //c = c*2 + 1;  same as above\n    return N ^ c;  \n    //return c - N; // also ok  \n  }\n};\n```\n\nSolution 2: math based solution: log2, pow\n\n```\nclass Solution { //math based solution: log2, pow\npublic:\n    int bitwiseComplement(int N) {        \n        if(N == 0) return 1;\n        int exponenet = (int)log2(N)+1;\n        int flipper = (int)pow(2, exponenet)-1;            \n        return N ^ flipper;\n    }\n};\n```\n\nWhat, the above two solution is still too anti-human?!\nOf course, it is.\nIf you are still not comfortable with the above two methods due to too much specific knowledge about bit operation,\nyou might find the last solution might be more natural :\n\nSolution 3:  naive simulation: find each single digit, then flip it\n```\nclass Solution { // BEST1: find each single digit, then flip it\npublic:\n    int findComplement(int num) {\n        int res = 0, ind = 0;\n        while(num > 0){\n            //find single digit from low to high significance\n            int digit = num % 2; \n            int flippedDigit = (digit == 1? 0 : 1); // flip digit\n            res += (flippedDigit << ind);\n            num /= 2;            \n            ind++;\n        }\n        return res;\n    }\n};\n\n```\nThis is a bonus solution: \n\nSolution 4:  Get all-1 mask by spreading 1 from most significant to the rest\n```\nclass Solution { // Get all-1 mask by spreading 1 from most significant to the rest:\npublic://Time/Space: O(1); O(1)\n    int findComplement(int num) {\n\t    if(num ==0) return 1;\n        int mask = num;\n        mask |= mask >> 1;\n        mask |= mask >> 2;\n        mask |= mask >> 4;\n        mask |= mask >> 8;\n        mask |= mask >> 16;\n        return num ^ mask;\n    }\n};\n\n```\nExplanation: \n\nTo understand the solution, we need to go backwards. The aim is to xor the given number with a mask. The mask should contain all 1s in its rightmost bits. However, the number of rightmost bits is important. In the case of 5(101), for example, the number of rightmost bits must be 3, since 5 uses 3 rightmost bits. The mask must be 111 for 5(101). When we xor 111 with 101, we will get 010. As another example, the mask will be 111111 for 38(100110)\n\nSo the problem boils down to generating the mask. Let\'s think about 8-bit numbers. We can later extend the same logic to 32-bit integers. I will count the bits from right to left, starting with 1.\n\nThe largest positive numbers represented by 8 bits will set 7th bit to be 1.\nIn binary format, they should be like:\n01ABCDEF\nwhere A,B,C,D,E,and F might be 0 or 1 and doesn\'t matter.\n\nThe first operation, mask |= mask>>1; will set the 6th bit. So, mask will become (011bcdef). Once again, we do not care the actual value of c,d,e,f.\nNow, we know that the 7th and 6th bits are set, we can safely shift the mask to right by not 1 but 2 bits. mask |= mask>>2; will now set the 5th and 4th bits. \nBy the same reason, we can now shift the mask to right by not 1, 2 or 3 but 4 bits. \nThat is the threshold for 8-bit numbers. We do not need to shift more.\n\nThe following is a detailed illustration with an example:\n\n```\nNote1: 8-bit: 2^7-1, the large number is: 127\nNote2: the first few positive numbers in 8-bit, must be in the format like: 01ABCDEF, where A,B,C,D,E,F belongs to [0,1]\nFor example: \n127 is: 01111111\n126 is: 01111110\n125 is: 01111101\n..\n\n\nLet\'s assume: num = 64 to make our point:\nmask =  num;  // this ensure the highest significance digit is same as that of num.\n\n01ABCDEF  (mask, we do not the value of A,B,C,D,E,F)         \n\nIllustration of operation: mask |= mask >> 1;\n01ABCDEF\n 01ABCDE\n---------- OR\n011?????\n\nIllustration of operation: mask |= mask >> 2;\n011?????\n  011???\n---------- OR\n01111???\n\nIllustration of operation: mask |= mask >> 4;\n01111???\n    0111\n---------- OR\n01111111\n\nWe found our goal: \n01111111\n\n```\n\n\n\n\nFor 32-bit integers, the shift operations should continue until reaching to 16. For 64-bit longs, that will be 32.\n\n\nReference/Credit:\nhttps://leetcode.com/problems/number-complement/discuss/96103/maybe-fewest-operations\n
['Simulation']