C++, 1-liner, 9 CPU instructions, and future (C++20) solution
This is a complement of the other "standard solutions". If you haven\'t yet, go read the solution or other posts first, please.\n\nSince this solution uses eith
> This is a complement of the other "standard solutions". If you haven\'t yet, go read the solution or other posts first, please.\n\nSince this solution uses either a C++20 function `std::countl_zero()` (at this point of time, it seems even the latest GCC (10.2) hasn\'t implement it, Microsoft added it in VS2019 version 16.8 preview 2 just last month!) or a built-in function, please read this post just for fun. Or maybe come back in two years :)\n\n----\n### Version 1\n\nIf we have C++20:\n```cpp\n    return N ? ((1 << (32 - countl_zero(N))) - 1) ^ N : 1;\n```\nFor now (gcc9), below will work:\n```cpp\n    return N ? ((1 << (32 - __builtin_clz(N))) - 1) ^ N : 1;\n```\n\nThis version was inspired by the approach 3 from the [solution](https://leetcode.com/problems/complement-of-base-10-integer/solution/):\n```java\n// Java\nclass Solution {\n    public int bitwiseComplement(int N) {\n        return N == 0 ? 1 : (Integer.highestOneBit(N) << 1) - N - 1;\n    }\n}\n```\n\nLater I realised that it can be better!\n\n### Version 2\n\n```cpp\n    // C++20\n    return N ? (0xFFFFFFFF >> countl_zero(N)) ^ N : 1;\n    // GCC9\n    return N ? (0xFFFFFFFF >> __builtin_clz(N)) ^ N : 1;\n```\n\n### Version 3-beta\n\nNow, are we able to eliminate the `ifelse`/`?:` branching?\nWhy not? We can just make the least significant/right most bit of the mask always 1. Easy!\n```cpp\n    // C++20\n    return ((0xFFFFFFFF >> countl_zero(N)) | 1) ^ N;\n    // GCC9 (won\'t work on Leetcode! See note below)\n    return ((0xFFFFFFFF >> __builtin_clz(N)) | 1) ^ N;\n```\nNote since LeetCode OJ compiles C++ with the `-fsanitize=undefined` flag, it will throw runtime error if passing 0 to `__builtin_clz()`\nBut don\'t worry! We can tweak the input!\n\n### Version 3\n\n```cpp\n    // C++20\n    return (0xFFFFFFFF >> countl_zero(N | 1)) ^ N;\n    // GCC9\n    return (0xFFFFFFFF >> __builtin_clz(N | 1)) ^ N;\n```\nExplain: for N > 1, changing the last bit will not effect the number of leading 0s, and for both 1 and 0 we use the same mask `0x1` (ie, `0xFFFFFFFF >> 31`).\n\n----\n### Performance\n\nSo how much have we improved?\nWe know approach 4 from the solution (for non-premium users who can\'t read the solution, see reference below) is faster than any other approaches since it doesn\'t have any loop or call any other functions like `log()` (Note `__builtin_clz()` is a builtin function that translates to **one single CPU instruction** `BSR` (bit scan reverse))\nI counted number of lines in assembly code and CPU instructions the code compiled into (GCC 10.2):\n\n|                     | # Lines of assembly code | # CPU instructions |\n| ------------- | ---------------------------- | -------------------- |\n| Approach 4 |                                     25 |                           23 |\n| Version 1     |                                     16 |                          14 |\n| Version 2     |                                     14 |                          12 |\n| Version 3     |                                       9 |                            9 |\n\nReference:\nApproach 4:\n```cpp\nint bitwiseComplement(int N) {\n    if (N == 0) return 1;\n    int bitmask = N;\n    bitmask |= (bitmask >> 1);\n    bitmask |= (bitmask >> 2);\n    bitmask |= (bitmask >> 4);\n    bitmask |= (bitmask >> 8);\n    bitmask |= (bitmask >> 16);\n    return bitmask ^ N;\n}\n```\n\n----\n## Further thoughts\n\nSince `std::countl_zero()` is a template, which can handle any type of integral values, can we do that as well?\nBelow will do:\n\n```cpp\ntemplate <class T>\nint bitwiseComplement(T N) {\n    return (numeric_limits<make_unsigned<T>::type>::max() >> countl_zero(N | 1)) ^ N;\n}\n```\nNote this requires C++20.\nSince `__builtin_clz()` is only for `int` (`__builtin__clzl()` for `long` and `__builtin__clzll()` for `long long`), it\'ll be trickier to make it happen. That\'ll be too far from the scope of this problem, so I\'m stopping here.\n\nEnjoy :)\n
['C']