Interview Question | Sum of Two Integers | Binary | C++
class Solution {
public:
int getSum(int a, int b) {
int sum = a;
while (b != 0)
{
sum = a ^ b;//calculate sum of a and b without thinking the carry
b = (a & b) << 1;//calculate the carry
a = sum;//add sum(without carry) and carry
}
return sum;
}
};English :
- a ^ b we know gives us sum value WITH ALL DIGITS ADDED without carry: 0 ^ 0 = 0 , 1 ^ 0 = 1, 0 ^ 1 = 1, 1 ^ 1 = 0, this is what the sum of each digit should be without thinking of the carry.
- How to get carry of each digit position? we do & of course. 1 + 1 is the only combination that gives a carry: so we use 1&1 because only with & operator you get 1 when 1&1 and you get 0 for all other combinations. This stuff is obvious.
- Why left shift? because each carry digit has to be added to the sum of the immediate left digits.
- Why b == 0 at some point? Because you could have the carry being added to a sum and still generate a carry. Think of this situation 1+0+1 or 0+1+1 or 1+1+1 or 1+1+0. In these cases you will have another carry that has to be further added.
- At some point when all carries from subsequent additions will be done being properly added within the final result, there will be no more carries in the addition. At this point your sum becomes the final answer and the number which is supposed to be the carry becomes 0. At this point b ==0.
Hindi :
a ^ b, जैसा कि हम जानते हैं, हमें सभी अंकों को जोड़ने के साथ एक योग मान देता है, जिसमें कैरी नहीं होता है: 0 ^ 0 = 0, 1 ^ 0 = 1, 0 ^ 1 = 1, 1 ^ 1 = 0, यह बिना किसी कैरी के प्रत्येक अंक का योग होना चाहिए।
प्रत्येक अंक स्थिति का कैरी कैसे प्राप्त करें? हम निश्चित रूप से & करते हैं। 1 + 1 एकमात्र संयोजन है जो कैरी देता है: इसलिए हम 1&1 का उपयोग करते हैं क्योंकि केवल & ऑपरेटर के साथ आपको 1 मिलता है जब 1&1 और आपको अन्य सभी संयोजनों के लिए 0 मिलता है। यह सामान स्पष्ट है।
लेफ्ट शिफ्ट क्यों? क्योंकि प्रत्येक कैरी अंक को तत्काल बाएं अंकों के योग में जोड़ा जाना है।
क्यों b == 0 कुछ बिंदु पर? क्योंकि आपके पास योग में जोड़ा जा रहा कैरी हो सकता है और फिर भी कैरी उत्पन्न कर सकता है। इस स्थिति के बारे में सोचें 1+0+1 या 0+1+1 या 1+1+1 या 1+1+0। इन मामलों में आपके पास एक और कैरी होगा जिसे आगे जोड़ा जाना है।
किसी बिंदु पर जब बाद के जोड़ से सभी कैरी अंतिम परिणाम के भीतर ठीक से जोड़े जाने पर किए जाएंगे, तो जोड़ में कोई और कैरी नहीं होगा। इस बिंदु पर आपका योग अंतिम उत्तर बन जाता है और जिस संख्या को कैरी माना जाता है वह 0 हो जाता है। इस बिंदु पर b ==0।
Hinglish :
A ^ B ka matlab hai ki hum dono digits ko add karte hain aur carry nahi karte hain: 0 ^ 0 = 0, 1 ^ 0 = 1, 0 ^ 1 = 1, 1 ^ 1 = 0. Yeh har digit ka sum hai agar carry ke baare mein na socha jaye.
Carry ke bare mein kaise pata karein? Iske liye hum & operator ka use karte hain. 1 + 1 hi ek combination hai jismein carry generate hota hai: isliye hum 1&1 ka use karte hain, kyonki sirf & operator ke saath hi 1&1 me 1 aata hai aur dusre sabhi combinations me 0 aata hai. Yeh toh obvious hai.
Left shift kyon karte hain? Kyonki har carry digit ko uske immediate left digits ke sum mein add karna hota hai.
B == 0 kab hota hai? Kyonki carry ko sum mein add karne ke baad bhi carry generate ho sakta hai. Is situation ke baare mein socho 1+0+1 ya 0+1+1 ya 1+1+1 ya 1+1+0. In cases mein tumhare paas ek aur carry hoga jise tumhe further add karna hoga.
Kabhi ek point aayega jab subsequent additions se aane wale saare carries final result mein add ho chuke honge aur ab addition mein koi aur carry nahi hoga. Is point pe tumhara sum final answer ban jayega aur woh number jise carry supposed tha woh 0 ban jayega. Is point pe B == 0.
