why leftmost works | what happens when we add 1 to a number | Proof
In binary addition, adding 1 to a number follows rules very similar to how addition works in decimal, but with only two digits (0 and 1). Let\'s take a deeper l
In binary addition, adding `1` to a number follows rules very similar to how addition works in decimal, but with only two digits (`0` and `1`). Let\'s take a deeper look at what happens bit by bit when we add `1` to a binary number.\n\n#### Binary addition works with the following basic rules:\n\n- 0 + 0 = 0\n- 0 + 1 = 1\n- 1 + 0 = 1\n- 1 + 1 = 10 (This results in 0 and carries over 1 to the next higher bit) So adding 1 in a 1 gives 2 in decimal format and 10 in binary.\n\nNow Lets see how does this help us,\n\nTake Example of `47` = `101111` there is always a number n-1,  here `46` to give answer ,as `46` is even and even number has last bit always `0` ,`46` = `101110` so when you `or` both the numbers, last bit gets set and you get `47` and `46` becomes your answer.\n\nBut can we do better,\nYes by using the binary addition trick we discussed above, we want answer to be minimum so what if we set the `1` which is just after the leftmost `0` to `0`. If we do this in `47` = `101111` then the binary will change to `100111`=`39` now if you add `1` to `39` then it bits will change with the last `1` to `0` then second last `1` to `0` then third last`1` to `0` and finally fourth last `0` will become `1` due to carry finally making `101000` = `40` and if you or `39` with `40` you will get `47`  \n\nbelow is just the implementation of this\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int number(int n){\n        int mask = 1;\n        for(int i=1;i<=31;i++){\n            mask = mask << 1;\n            if((n&mask) == 0){\n                mask = mask >> 1;\n                return n & ~(mask); \n            }\n        }\n        return 0;\n    }\n\n    vector<int> minBitwiseArray(vector<int>& nums) {\n        vector<int> ans;\n        for(auto& it: nums){\n            if(it == 2){\n                ans.push_back(-1);\n            }else{\n                ans.push_back(number(it));\n            }\n        }\n        return ans;\n    }\n};\n```
['Math', 'Bit Manipulation', 'C++']