[Animated Video] Bit Manipulation & Masking Visualized
CodeInMotion ResourcesEvery Leetcode Pattern You Need To Knowhttps://www.blog.codeinmotion.io/p/leetcode-patternsBlind 75 Animated Playlisthttps://www.youtube.c
![Code In Motion Purple Transparent Background (2).png](https://assets.leetcode.com/users/images/69a60a6b-9c0f-4aa1-899b-98ee5f9b1dc1_1733778334.1189735.png)\n\n# *CodeInMotion Resources*\n## Every Leetcode Pattern You Need To Know\nhttps://www.blog.codeinmotion.io/p/leetcode-patterns\n\n## Blind 75 Animated Playlist\nhttps://www.youtube.com/playlist?list=PLHm8nzcbp3_19DiTlDg8QYvR-hN5jzPCp\n\n## Subscribe to YouTube\nhttps://www.youtube.com/@CodeInMotion-IO?sub_confirmation=1\n\n---\n## Animated Video\nhttps://youtu.be/mXB9jbJzXwU\n\n## Intuition\n![chrome_SFknFfWZ8s.png](https://assets.leetcode.com/users/images/66e78c3d-0fec-4c27-bf62-27785d711cd9_1733891538.6256926.png)\nTo solve the problem of summing two integers without using the `+` or `-` operators, we can utilize bitwise operations. The key is to understand how binary addition works:\n- The XOR (`^`) operation gives the sum without carrying over.\n- The AND (`&`) operation identifies where the carry occurs.\n- Shifting the carry by one bit (`<<`) simulates carrying over to the next significant bit.\nWe repeat this process until there are no more carry operations left.\n\n## Approach\n1. Use a 32-bit mask (`0xFFFFFFFF`) to handle negative numbers and simulate a 32-bit integer.\n2. Perform the addition using XOR for the sum and AND for the carry.\n3. Shift the carry by one position to the left.\n4. Update the operands with the new sum and carry.\n5. Repeat until the carry becomes zero.\n6. Adjust for negative numbers if the result exceeds the maximum 32-bit integer.\n\n## Example Walkthrough\n### Input: `a=3`, `b=5`  \nBinary representation:  \n- `a = 0011`  \n- `b = 0101`  \n\n**Step 1:**  \n- XOR (`^`): `0011 ^ 0101 = 0110` (sum without carry)  \n- AND (`&`): `0011 & 0101 = 0001` (carry)  \n- Shift carry: `0001 << 1 = 0010`  \n\n**Step 2:**  \n- Update `a = 0110` and `b = 0010`.  \n- XOR: `0110 ^ 0010 = 0100`  \n- AND: `0110 & 0010 = 0010`  \n- Shift carry: `0010 << 1 = 0100`  \n\n**Step 3:**  \n- Update `a = 0100` and `b = 0100`.  \n- XOR: `0100 ^ 0100 = 0000`  \n- AND: `0100 & 0100 = 0100`  \n- Shift carry: `0100 << 1 = 1000`  \n\n**Step 4:**  \n- Update `a = 0000` and `b = 1000`.  \n- XOR: `0000 ^ 1000 = 1000`  \n- AND: `0000 & 1000 = 0000` (no carry left).  \n\n**Result:** `a = 1000` (decimal `8`).\n\n## Python-Specific Explanation\n\nPython handles integers differently compared to other programming languages. Python integers are **not limited to 32-bits** and can grow arbitrarily large. However, in this problem, we need to simulate **32-bit integer behavior**, where integers are bounded to 32 bits and can represent both positive and negative values. This requires additional handling in Python using a **mask** and the concept of **two\'s complement** for signed integers.\n\n### What is a Mask?\nA **mask** is a bit pattern used to isolate or manipulate specific bits of a number. In this solution, we use the mask `0xFFFFFFFF`, which represents a 32-bit binary number of all 1\'s (`11111111111111111111111111111111` in binary). \n\nThis mask helps us:\n1. Ensure all calculations stay within 32 bits.\n2. Handle signed numbers by simulating the boundaries of 32-bit integers.\n\n#### Why AND the Results with the Mask?\nWhen performing bitwise operations in Python, numbers can exceed 32 bits. To restrict results to 32 bits, we use the bitwise AND operator (`&`) with the mask. You can imagine that since the mask is only 32 bits, AND\'ing a number with a mask forces us to only use 32 bits.\n```python\nmask = 0xFFFFFFFF # 1111 .... 1111, 32 ones\nnumber & mask # we effectively trim the number to only use 32 bits\n```\n\n#### Why Flip the Bits and Take Two\'s Complement?\nIn Python, numbers are treated as unsigned by default, meaning Python will interpret all binary representations as positive integers. To simulate signed 32-bit integers (e.g., negative numbers), we need to handle cases where the result of our operation exceeds the maximum positive value of a 32-bit integer `(2^31 - 1)`.\n\nHere\u2019s the process:\n1. If the result of the computation exceeds the 32-bit signed integer max `(2^31 - 1)`, we know it\u2019s a negative number in the context of 32-bit integers.\n2. To convert this value into its correct signed representation, we invert its bits using a bitwise XOR with the mask `0xFFFFFFFF`:\n```\n# this example assumes an int is 4 bits instead of 32 for easier reading\nmask = 1111\na =    1100 # python treats this as 12 in unsigned format\nflipped_bits = a ^ mask = 0011\n```\n3. Next, we re-flip back the bits using python\'s two complement operator to force python to treat the number as a signed, negative value\n```\n# ~ is the 2s complement operator in python. ~x = -x-1 \nflipped_bits = a ^ mask = 0011\n~flipped_bits = ~(a ^ mask) = 1100 # python now treats this as -4\n```\n4. Therefore, if our final sum is less than `2^31 - 1`, we return back the answer, else we return back `~(a ^ mask)`\n\n## Complexity\n- Time complexity: $$O(32)$$\n- Space complexity: $$O(1)$$\n\n## Code\n```Python []\nclass Solution:\n    def getSum(self, a: int, b: int) -> int:\n        mask = 0xFFFFFFFF  # 32 bit mask\n        maxInt = 2**31 - 1\n\n        while b != 0:\n            sum = (a ^ b) & mask # contain to 32 bits\n            carry = (a & b) & mask # contain to 32 bits\n            a = sum\n            b = carry << 1\n        \n        return a if a <= maxInt else ~(a ^ mask)\n```\n```Java []\nclass Solution {\n    public int getSum(int a, int b) {\n        while (b != 0) {\n            int sum = a ^ b; // sum without carry\n            int carry = (a & b) << 1; // carry shifted left\n            a = sum;\n            b = carry;\n        }\n        return a;\n    }\n}\n```\n```JavaScript []\nvar getSum = function(a, b) {\n    while (b !== 0) {\n        let sum = a ^ b; // sum without carry\n        let carry = (a & b) << 1; // carry shifted left\n        a = sum;\n        b = carry;\n    }\n    return a;\n};\n```\n```C# []\npublic class Solution {\n    public int GetSum(int a, int b) {\n        while (b != 0) {\n            int sum = a ^ b; // sum without carry\n            int carry = (a & b) << 1; // carry shifted left\n            a = sum;\n            b = carry;\n        }\n        return a;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int getSum(int a, int b) {\n        while (b != 0) {\n            int sum = a ^ b; // sum without carry\n            int carry = (a & b) << 1; // carry shifted left\n            a = sum;\n            b = carry;\n        }\n        return a;\n    }\n};\n```\n```Go []\nfunc getSum(a int, b int) int {\n    for b != 0 {\n        sum := a ^ b // sum without carry\n        carry := (a & b) << 1 // carry shifted left\n        a = sum\n        b = carry\n    }\n    return a\n}\n```\n### Please thumbs up on the bottom-left corner!<br>It motivates me to create more solutions & videos for you!\n![thumbs up (1).png](https://assets.leetcode.com/users/images/f69ffdba-12f7-4f5b-8950-e7d3bd77c52a_1733768002.4687448.png)\n
['Math', 'Bit Manipulation', 'Python', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'C#']