Add Two Numbers Without The "+" Sign (Bit Shifting Basics)

[@BackToBackSWE]

Table of Contents The Problem Introduction 0:00 - 0:51 A Way To Think About Number Bases 0:51 - 3:56 Back To The Problem At Hand 3:56 - 4:16 Let's Add Some Numbers (Decimal, Base 10) 4:16 - 4:59 Let's Add Some Numbers (Binary, Base 2) 4:59 - 7:40 Bit Shifting Operators: The 'AND' -> '&' 7:40 - 9:41 Bit Shifting Operators: The 'XOR' -> '^' 9:41 - 11:36 Bit Shifting Operators: The 'Left Shift' -> '

[@danavram8437]

What do you mean? It also works on negative numbers (great explanation of the whole process btw :) ). I used this algorithm on leetcode in C++ (and it has to work with negative numbers as well). The only catch is that I had to convert the carry to unsigned when doing the left bitshift (which wraps the bits around with 1111....11 (32 bits)) int getSum(int a, int b) { while(b) { int carry = a & b; // get all carry bits (all 1&1s) a = a^b; // sum of disjoint bits (everything except what needs to be carried) // shift carry by one, as this is how a regular sum operation works // the carry is moved to the next position b = (unsigned)carry

[@BackToBackSWE]

yeah

[@arunprakash1101]

Hey !! This explanation is excellent! But I can't see the code for this problem in the description! Is it moved?

[@willinton06]

Arun Prakash same here

[@anjalibelani5101]

Thank you for these videos. However, I dont see the code in the description in any of your videos. Am I missing something?

[@minhazulislam4682]

dude, you need to come back and teach us. the world needs more people like you, blackpenredpen, the organic chemistry teacher, 3blue1brown, nick white, tech with tim, jenny it and many more.

[@albertjtyeh53]

is he working at FAANG now?

[@MrACrazyHobo]

@@albertjtyeh53 Back To Back SWE is at twitter!

[@dubey_ji]

Corey Schafer and Sentdex are great too

[@rtothec1234]

I took compsci and learned this but could never explain to my friend who couldn’t grasp it. She struggled the whole time. This is such a great explanation and you are an excellent teacher.

[@null5245]

u r a good teacher bro! Actually i came here because of your comment in leetcode lol :)

[@BackToBackSWE]

nice

[@angelanayiga4060]

@@BackToBackSWE I do agree you should make comments on all leet code questions you've solved! That's how I landed on B2B SWE!

[@BackToBackSWE]

@@angelanayiga4060 hey

[@harshag5423]

@@angelanayiga4060 Now because of your comment I landed on B2B which I didn't even know.

[@angelamukisa4433]

Harsha G I’m really glad you landed on it and I hope it helps you the way it helped me 🤗🙏🏾

[@baichen6449]

your explanation really helps people who were totally lost, like me.

[@BackToBackSWE]

nah, ur good

[@anniewiley1425]

Hey man I just wanted to say I think these videos are immensely helpful. The way you explain your thought process on these complex but tiny subjects rashly helps a person change the way they think about code, not to mention learning the lingo of a SWE. Also please don't ever lose the awkward endings and outtakes.

[@SR-we1vl]

Whenever I get stuck on a problem and see if your video is there, I'm relieved! Thank you man!

[@BackToBackSWE]

Nice sure

[@cuteypatootie]

I have spent literal years glossing over bitshifting because no explanation could come close to me understanding it. I now have at least a basic knowledge and a starting place. Thank you!

[@donurukirankumarreddy8872]

The best teaching that I have seen in my life till now is yours .

[@BackToBackSWE]

thanks

[@vS-xv7vm]

Explanation is so good that we won't need to write code for this in interview - just a dry-run with example would do.

[@BackToBackSWE]

ye

[@haleygu2171]

Faced this problem in an interview with Qualcomm ... I wish I could see this video earlier to come up with bit manipulation solution :( Thanks a lot for clear explaination!

[@BackToBackSWE]

nice

[@prithazz]

This is a stupid interview question to ask.. honestly, they don't deserve you.

[@snlagr]

@@prithazz maybe they wanted to check low level understanding

[@calvinchankf]

To begin with, here is an intuitive approach for this question. This is not optimal, but its easier to understand and present to your interviewer(at the beginning) def addTwoNumbersWithoutPlus(a, b): arr = [] carry = 0 while a > 0 or b > 0: # get the least significant digit of a x = 0 if a > 0: x = a & 1 a >>= 1 # get the least significant digit of b y = 0 if b > 0: y = b & 1 b >>= 1 # add them by using a naive hard-coded table num, carry = add(x, y, carry) arr.append(num) # append the carry if it exists if carry > 0: arr.append(1) # binary to int res = 0 for i in range(len(arr)): res += arr[i] * 2**i return res def add(a, b, carry): m = { (0, 0, 0): (0, 0), (0, 1, 0): (1, 0), (1, 0, 0): (1, 0), (1, 1, 0): (0, 1), (0, 0, 1): (1, 0), (0, 1, 1): (0, 1), (1, 0, 1): (0, 1), (1, 1, 1): (1, 1), } return m[(a, b, carry)]

[@BackToBackSWE]

nice

[@CodingForRealLife]

Now I understand a lot of techniques that I wasn't able to understand before by following your channel, keep it up!

[@BackToBackSWE]

nice

[@datle5503]

This is the ultimate guide to this hell of bits manipulation. Thank you so much.

[@ZhenyaVlasov]

Thanks for your vids. I found some inconsistencies with your explanation. At 11:48 you say that when we do shift, '1 gets shifted out'. However, it doesn't. As an example, take 0101 (5) and 1101(13) When shifting, we add 0 on the right side and if carry started with 1, it will grow as well. We can't loose the first 1 because just like other 1s in the carry, it specify an index where we need to carry over. In the provided github code, line 134, it says "1 got shifted out". Again, if we shift it, we will loose part of our answer. The reason why, at some point, 'carry' becomes 0 and we brake out of the loop, because on 3rd iteration after increasing the carry by one more digit, we will be performing '&' operation between 4 digit (0010) and 5 digit (10000). The result of it will be 00000. Result of the '^' operation will be 10010 (which, again, won't be possible if we lost that left most '1'. 'carry

[@BackToBackSWE]

Woah, a lot to parse, will need to jog my memory on this one. And nice, hey, I'm in Maryland rn so oof

[@hoboshenanigans]

Dude keep it up, i've learned more from you then my attempt at graduate school lol

[@BackToBackSWE]

ha nice

[@janmichaelaustria620]

Likewise!

[@OhsoLosoo]

Using that ad to cover the redundant statement was brilliant lmao. I would've never noticed it was repeated if you didn't point it out honestly.

[@Mysticbeing21]

Ive learnt alot today. Ive been struggling these days and i was almost burn out because of the amount of unfinished projects i had. Thank you

[@BackToBackSWE]

Happy to help

[@ShuangyiHu]

You are such a good teacher! Thanks for breaking down the basics and emphasizing the details!

[@ハイらムハイマん]

My Brother, since college back in 1999, I haven't had to use it. But, you have refreshed my way of thinking. Thanks and continue to progress forward!!!!

[@maxxxxx93]

very well explained solution! i think it’s worth noting that this only really works with positive integers

[@BackToBackSWE]

Yeah, true, I'll add that to the notes.

[@Oda3908]

5 steps: 1. base 10 to base 2 2. while carry > 0 3. carry = a & b 4. b = a ^ b 5. a = carry k = x * (1/2)^k, note that right shift will cut off the decimal part, e.g. 20 >> 3 => 20 * 1/8 => 2.5 = 2

[@finiteimpulse3765]

A short video like this about Two's complement would be great.

[@BackToBackSWE]

ok

[@musicvoice3030]

Genuinely explained. Excellent, keep doing your work. You`re a great teacher.

[@BackToBackSWE]

thanks.

[@zelmagarza]

Great vid! Why isn't it enough to do the following? int whereCarry = (a & b)

[@BackToBackSWE]

I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.

[@a.yashwanth]

Because when you use | it does not add two numbers. If it adds, then we would use a|b directly.

[@OhsoLosoo]

Love you man. I'm in Graduate school & your videos have helped me so much.

[@thev01d85]

You are extremely talented at teaching this stuff, I have struggled with bitwise operations for a while now, however after watching your explanation I was able to implement this myself, which is a major break through. Thank you for this video!

[@BackToBackSWE]

Glad to know we could help!

[@skullTRTR]

Wow finally found someone who can explain things on youtube. Thanks.

[@BackToBackSWE]

sure

[@skullTRTR]

@@BackToBackSWE youtube needs someone who can explain system design questions as well.

[@BackToBackSWE]

@@skullTRTR Gaurav sen

[@popoffs5273]

You just explained how computers add on a fundamental level. Well done

[@matthewpourroy1342]

Back To Back SWE + Leetcode + Cracking the Coding Interview = Total Interview prep package

[@pritomdas6215]

wow...it did take me a lot of rewinding to understand, but thanks to God I finally could get the whole picture of how it works.

[@BackToBackSWE]

nice

[@youarecorrectiamwrongbecau1338]

Watched on C computer Opened KZbin on phone just to like the video Then thought you are really good so suscribed also And and and ... (redundant) I understand why these kind of stuffs are generally not well explained or no one does some hard work on it because everyone thinks that other DS&A are more important and they mostly form important questions but this concept was required in a programming question where looking to solve at the problem from this perspective seemed improbable. But normal bitwise loop operation would exceed the time limit. The only way was to understand thoroughly how the shifting works and then solve the question in a completely different way and then it passed within time limits. Keep posting concepts like these because they form really difficult questions.

[@BackToBackSWE]

Thx and ok

[@kevinkkirimii]

I start so well, then I just get lost. I have to find a way to get this concepts in my head permanently.

[@CHIRANJIBNANDY1]

Bro...u r a genius.... thanks for making me prepared.

[@BackToBackSWE]

nice! good luck

[@PheezxCoding]

Your explanations are always so clear and engaging.

[@AlexanderFilippov-ua]

This is the best explanation I've ever seen! Thanks a lot!!!

[@BackToBackSWE]

sure

[@jeromepowell1423]

Great video. Speaking the entire process through like the computer solidified it for me.

[@waiyanleung5199]

Totally understood from zero background. Thumbs up!

[@BackToBackSWE]

nice

[@vishaltambrahalli3461]

Not able to find the code in the description! Can some let me know if I'm missing something?

[@firedragontamer8330]

Very helpful but the code examples are missing from the description, were they removed?

[@brandongagon]

"A problem well stated is a problem half solved" -Charles F. Kettering

[@stevenalexander6262]

i need to remember this...

[@BackToBackSWE]

ye

[@imagineabout4153]

I just started to study this stuff and my mind is like seeing the light

[@AarshSharma]

Haven't seen a better explanation. Kudos.

[@BackToBackSWE]

thanks

[@qiskko]

This is great! but I wish you put the code in your video rather than in the description.

[@BackToBackSWE]

yeah got it

[@yega3k]

I just tried this in Python. It feels like voodoo! a = 1 b = 3 while True: # 1. carries first c = a & b # 2. sum with XOR a = a ^ b if c == 0: print(‘ans:’, a) # no carries left, print ans: 4 break # 3. shift carries by one position to the left b = c

[@BackToBackSWE]

ye

[@erickbarbosa5476]

This guy was born to teach!

[@BackToBackSWE]

yis he wuz

[@cristianouzumaki2455]

This couldn't have been explained any better.

[@BackToBackSWE]

eh maybe it could've

[@sanapalavenkatesh5273]

Awesome explanation.. By the way once again thank you for ...

[@vivaanbaid9975]

love this channel!

[@BackToBackSWE]

thanks buddy! try our 5 day free mini course for some awesome content - backtobackswe.com/

[@anujagrawal60]

Never saw a better explanation than this👏👏👏

[@BackToBackSWE]

thanks

[@mallikarjunpidaparthi]

Wow. You made it so simple. Thank you sir.

[@humengineerhaijholalekarni8408]

OMG came from Geeksforgeeks. Thank you so much sir.

[@BackToBackSWE]

sure

[@VladimirTheAesthete]

That's a pretty intuitive explanation here!

[@PiBiNi]

Loved the way you explained even the basics. Thank you.

[@BackToBackSWE]

sure

[@dicointech]

Great video. It would be better if you say & is to find 1&1. For example , when 01 + 11, we need to carry at 0&1 as well because of carry from 1&1

[@BackToBackSWE]

Good point. I'll keep this in mind. Though, I feel like 7:52 and 8:32 explain that clearly.

[@Cyber99221]

Oh wow! Cool, this was a nice refresher. Great video

[@jkim5118]

I am always impressed with your videos. How do you choose the questions? It seems like you have a set of question that you plan to cover and I can feel that those questions are more relevant to actual skills that we need for interviews (not like brain teasers). Also, what's your plan after to cover all planned questions?

[@BackToBackSWE]

I built a list of like 300 when I started this channel. But at some point I just started doing the most burning questions that I felt that I just HAD to try to cover. And as for plans after I have many questions covered...eh, I don't know. Here is my rough plan for this project: backtobackswe.com/plans I don't think any human can ever cover all questions. But they can cover all topics and concepts. This channel is far from the latter.

[@reemasharma6188]

You did such a great job at explaining this tedious problem. Please make a video on Dynamic programming concepts as well. :-)

[@BackToBackSWE]

ok

[@os2958]

much better than the technique taught in my grad class

[@omkargunjal1611]

Never thought about this logic 😯😯.... Amazing 😍😍

[@BackToBackSWE]

sure

[@harinijeyaraman8789]

This was super helpful !! You're amazing at teaching !

[@BackToBackSWE]

thanks - glad it helped

[@jhessikanda]

hey great video!!! I just couldn´t find the code in the description =(

[@xulinazrx]

You are awesome! Your presentation is so clear and easy to understand!

[@harshjoshi2523]

leetcode brings me here :) Thanks sir you are a good teacher :)

[@BackToBackSWE]

ya

[@sinify6676]

You always have good lectures here. Just something small (i know the video is old, but w/e): I think saying "how many of each value can we fit" is a bit misleading, since we only ever represent each place with 1 or 0. I personally think it makes more sense to scan from left to right, always checking if the current place fits into the number (updating the new target value as you did). I.e., if you follow this method, there should never come a time where you can fit MORE than 1 value, because that would imply you missed a higher value previously--if I can fit two 8's, I should have used 16.

[@deepamgoel5396]

Hey, thanks for the video! You're the best. Can you make more videos on bit manipulation please?

[@BackToBackSWE]

thx - thx - sure

[@Sarah-il5dr]

You are my go to when comes to all questions!

[@BackToBackSWE]

ye

[@amanzholdaribay9871]

Man, that's been interesting and fun to listen to you! Thanks! I got topic)

[@BackToBackSWE]

nice

[@tulufokaki6947]

Thank you so much, this solve my wondering for years as not an engineer

[@Firstusee256]

You helped a lot , thank you for making such kind of videos.....

[@BackToBackSWE]

sure

[@lets_see_777]

best explanation, subbed

[@BackToBackSWE]

thanks

[@top-list6450]

Thank you so much for the clear explanation. Could you please upload video on Division as well

[@BackToBackSWE]

yes

[@ranjanasinha]

Hi. Great Video. Could you please cover the scenarios involving negative numbers. I tried to solve this in python. It failed for the negative numbers.

[@BackToBackSWE]

yeah

[@VocalWithShubham]

As you have mentioned that this only works with positive integers. What about negative integers. How to add negative integers without using any arithmetic operators?

[@BackToBackSWE]

no idea

[@igo1071]

U R an excellent teacher 👍🏼thanks a lot ✔️

[@BackToBackSWE]

Thanks sure - parents....

[@hrithikdhanraj2919]

That's simply Great. I appreciate your work. Thanks for the explanation ♥️♥️

[@traveltechtaste41]

Thanks for explaining this so clearly

[@BackToBackSWE]

sure!

[@SpiffyFurFamily]

Best explanation I've seen. It helped me implement my C# program! Could you do a similar video for substraction without using arithmetic operators?

[@syedsafdarali4287]

The whole time i was thinking he is going to do a shitty approach of iterating through all the 31 bits But in the last when he used &^ and

[@asmitadhungana3790]

This was a real cool and intuitive explanation! Thanks!

[@BackToBackSWE]

Thank You, Glad you liked it. Do check out backtobackswe.com/platform/content and please recommend us to your family and friends :)

[@alex-gz7ud]

Thank you for the explanation!! You are awesome!!!

[@TheLovegarg]

the best video on this question

[@BackToBackSWE]

Thanks

[@demigod6190]

Thank you very much. Finally, I got the concept!

[@siddhantsharma4011]

Glad I found this channel. Truly amazing 🎉

[@BackToBackSWE]

Happy Halloween 🎃 Thank you for your kind words, Siddhant! Let us know other topics we could cover! We'd love to offer you 50% Off our exclusive lifetime membership use the code SPOOKY50 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SPOOKY50

[@namanshah9216]

What an explanation man! thank you ton!!

[@BackToBackSWE]

sure

[@cshivani]

Excellent, you have put in lot of effort in explaining it, thanks appreciate it!! :)

[@BackToBackSWE]

sure

[@pradhumansingh3933]

Thanks a lot.Ur explaination really cleared my doubt....

[@abhilashpatel3036]

So clearly explained, i can't thank enough. 👍

[@cozywanderer]

This was a fantastic explanation!!

[@BackToBackSWE]

thanks

[@Animax590]

you really helped with just simple concepts

[@shrutiagrawal6065]

this is really awesome. really loved it gr8 work!!!! all doubts are solved thanks..!!!!

[@BackToBackSWE]

sure

[@user-wb5ox7nw2u]

Man you are something else love from India 🇮🇳

[@aayush5474]

I am enjoying this more than netflix

[@BackToBackSWE]

great

[@rahulpothula1902]

The video is super helpful as usual... BTW, what's the name of the outro music??

[@girishthatte]

Awesome explanation covering from basics 🔥

[@BackToBackSWE]

thx

[@alexeydemyanchuk]

Best explanation, so thank you, man!

[@fangzhenghu6479]

Thanks! I wonder why a solution which supports negative integers is not discussed here? Is it because such a case is unlikely to present in an interview?

[@BackToBackSWE]

No, I just never solved it for that case, not sure how negatives would be accommodated without thinking on it for a bit

[@fangzhenghu6479]

@@BackToBackSWE That's fair. I saw an easy-understanding answer that handles the negative case, which you or other audiences might be interested in leetcode.com/problems/sum-of-two-integers/discuss/84290/Java-simple-easy-understand-solution-with-explanation/

[@shyammuppidi2092]

Awesome bro love all your videos

[@BackToBackSWE]

thank you.

[@punittiwari7557]

Can you please tell Is there is any way to know how many times this loop will run or execute???

[@BackToBackSWE]

uh

[@punittiwari7557]

@@BackToBackSWE I was solving a problem in which the question asked how many times this while loop will work and it is giving TLE if just count how many times it is executing... So I want to know "Is there is any way to directly know how many times this gonna be executed"...

[@sumitgupta2618]

@@BackToBackSWE he means how many time the iteration will happen until carry becomes zero?

[@prabhatkashyap8333]

Codechef question BINADD, www.codechef.com/DEC19B/problems/BINADD

[@femi_alogba]

Excellent teacher. Excellent!!