BItwise Operator, how does Left shift and right shift works

Question

public class Solution {
    public int GetSum(int a, int b) {
        while(b != 0) {
            int carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
        return a;
    }
}

So the question is to add two numbers without using arithmetic operators, I found a solution in leetcode discuss section but I am not sure how the carry variable works

It's an and operation bit by bit, so if you do 3 & 1 you'll get 1. — dcg, Dec 16 '19 at 17:19
id read your source article and work the math out by hand prior to attempting to understand the code. also check out https://stackoverflow.com/questions/11072202/what-is-the-purpose-of-bit-shifting for general bit shifting reasons. — Jeremy, Dec 16 '19 at 17:23
so adding bits means that 0 + 0 is 0, 0 + 1 is 1, and 1 + 1 is 10. So if a and b are 1 then the and will be 1 and the xor will be 0, so you want the 0 to be the result and carry the one shifted by one place. — juharr, Dec 16 '19 at 17:26
https://www.electronics-tutorials.ws/combination/comb_7.html — Hans Passant, Dec 16 '19 at 18:25

score 2 · Accepted Answer · answered Dec 16 '19 at 18:00

public class Solution {
    public int GetSum(int a, int b) {
       // Iterate till there is no carry 
        while(b != 0) {
            // carry now contains common 
            // set bits of a and b 
            int carry = a & b;
             // Sum of bits of a and  
            // b where at least one  
            // of the bits is not set 
            a = a ^ b;
            // Carry is shifted by  
            // one so that adding it  
            // to a gives the required sum 
            b = carry << 1;
        }
        return a;
    }
}

example

when you call sum function like this then

GetSum(60, 13)
/* 60 = 0011 1100 */  
/* 13 = 0000 1101 */

while(b != 0) (its while loop and it will loop until b becomes 0)

int carry = a & b;; // a=60 & 13

will become 12 /* 12 = 0000 1100 */

a = a ^ b;

will become 49 /* 49 = 0011 0001 */

b = carry << 1;

will become 24 because of Binary Left Shift Operator(<<). The left operands value is moved left by the number of bits specified by the right operand and it will loop and calculate continue like i explained

BItwise Operator, how does Left shift and right shift works

1 Answers1