Add Two Numbers Without The "+" Sign (Bit Shifting Basics)
HTML-код
- Опубликовано: 2 окт 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Add two integer values without using the "+" operator.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
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' -> '
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
yeah
Hey !! This explanation is excellent! But I can't see the code for this problem in the description! Is it moved?
Arun Prakash same here
Thank you for these videos. However, I dont see the code in the description in any of your videos. Am I missing something?
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.
is he working at FAANG now?
@@albertjtyeh53 Back To Back SWE is at twitter!
Corey Schafer and Sentdex are great too
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.
u r a good teacher bro!
Actually i came here because of your comment in leetcode lol :)
nice
@@BackToBackSWE I do agree you should make comments on all leet code questions you've solved! That's how I landed on B2B SWE!
@@angelanayiga4060 hey
@@angelanayiga4060 Now because of your comment I landed on B2B which I didn't even know.
Harsha G I’m really glad you landed on it and I hope it helps you the way it helped me 🤗🙏🏾
very well explained solution!
i think it’s worth noting that this only really works with positive integers
Yeah, true, I'll add that to the notes.
your explanation really helps people who were totally lost, like me.
nah, ur good
I start so well, then I just get lost. I have to find a way to get this concepts in my head permanently.
Bro...u r a genius.... thanks for making me prepared.
nice! good luck
Now I understand a lot of techniques that I wasn't able to understand before by following your channel, keep it up!
nice
You just explained how computers add on a fundamental level. Well done
Awesome explanation.. By the way once again thank you for ...
Wow finally found someone who can explain things on youtube. Thanks.
sure
@@BackToBackSWE youtube needs someone who can explain system design questions as well.
@@skullTRTR Gaurav sen
Totally understood from zero background. Thumbs up!
nice
Not able to find the code in the description! Can some let me know if I'm missing something?
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!
nice
This is a stupid interview question to ask.. honestly, they don't deserve you.
@@prithazz maybe they wanted to check low level understanding
Very helpful but the code examples are missing from the description, were they removed?
Dude keep it up, i've learned more from you then my attempt at graduate school lol
ha nice
Likewise!
Wow. You made it so simple. Thank you sir.
Thank you so much, this solve my wondering for years as not an engineer
I am enjoying this more than netflix
great
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
Woah, a lot to parse, will need to jog my memory on this one. And nice, hey, I'm in Maryland rn so oof
Oh wow! Cool, this was a nice refresher. Great video
Can you please tell Is there is any way to know how many times this loop will run or execute???
uh
@@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"...
@@BackToBackSWE he means how many time the iteration will happen until carry becomes zero?
Codechef question BINADD, www.codechef.com/DEC19B/problems/BINADD
Explanation is so good that we won't need to write code for this in interview - just a dry-run with example would do.
ye
Excellent video.
thx
A short video like this about Two's complement would be great.
ok
This was a fantastic explanation!!
thanks
The video is super helpful as usual... BTW, what's the name of the outro music??
This is great! but I wish you put the code in your video rather than in the description.
yeah got it
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?
No, I just never solved it for that case, not sure how negatives would be accommodated without thinking on it for a bit
@@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/
Please post a video on how to subtract two numbers without using arithmetic operators.pleaseeeeee :(
I cannot as of right now.
hey great video!!! I just couldn´t find the code in the description =(
I could not find the link to the code in the description. can someone please point me to the code? Thank you
The repository is deprecated - we only maintain backtobackswe.com now.
Great video man
Watched on C computer
Opened RUclips 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.
Thx and ok
That is an awesome explanation! Thanks!!!!
How can we guess as to how many iterations we need to get to the actual answer without doing the addition itself?
We can asymptotically upperbound the worst case
Doing codechef😂
@@govindsinghal7975 so u too came all the way here trying to figure out a way for "addition". C'mon man now u can get 100/100. 50 was way too easy.
@@aqib829 wut
@@aqib829 did you solve Easy Subsequence Selection
Your solution does not cover the edge case of when one or both integers are negative.
Addressed in pinned comment
leetcode brings me here :) Thanks sir you are a good teacher :)
ya
Great vid! Why isn't it enough to do the following?
int whereCarry = (a & b)
I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.
Because when you use | it does not add two numbers. If it adds, then we would use a|b directly.
Whenever I get stuck on a problem and see if your video is there, I'm relieved! Thank you man!
Nice sure
I don't see the code. Is this no longer available because you have made a company? If so, you should update this video because you reference the code a lot and people can't access without paying $100 which is fine, but there should be an update stating that the code is no longer available for free.
The repsoitory is deprecated - we only maintain backtobackswe.com now.
@@BackToBackSWE okay, thanks. I'll add the membership to my budget for next week. Thanks bro!
Hi I know that you use the 'and' operator to show the position you need to carry but how do you explain this to an interviewer? The 'or' operator with both ones give the same result (a one). Why not use the 'or' operator? I completely understand the solution, just wondering how to explain it to someone who's seeing the question for the first time. Thanks.
I can't reply to this but I saw it, I hope someone helps u
@@BackToBackSWE I figured it out. Thanks. Just a tip - with technical problems/algorithms it's better to show the code and walk through it to give the viewer the whole picture.
Title: addition without + sign
Me: 2-(-2)
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
Good point. I'll keep this in mind. Though, I feel like 7:52 and 8:32 explain that clearly.
Hey, thanks for the video! You're the best. Can you make more videos on bit manipulation please?
thx - thx - sure
It would be better if you can explain it with one negative number example as well.
yes - the given approach does not work for that
This is very helpful video but I am not seeing any code in description.
thx and the repository is deprecated we only maintain backtobackswe.com now
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.
yeah
nice explanation
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.
thank you
"A problem well stated is a problem half solved" -Charles F. Kettering
i need to remember this...
ye
really helpful!! TY
sure
You said you won't get into the other operators will you please rethink that .
ok
Mr man your too handsome to teach ok I tried to follow but I've been admiring till the end. Anyways God bless you
lol
Add 2 number without + sign
a+b = 2*a-(a-b)
yes
a-(-b) 😒
what is this sorcery?!
for real though thank you so much! great explanation!
sure
You did such a great job at explaining this tedious problem. Please make a video on Dynamic programming concepts as well. :-)
ok
Codification is a terrible choice of words for what you mean, which could be 'encoding', or 'conversion', which is really what you want.
>
idc
No one says "zor" for XOR. It's pronounced "ex-or"
well I do lol. but yeah I know
I'm currently at UTK and almost every person including the prof. says "zor" and "x-or" interchangeably. It provides fluidity when talking about it.
Thank u very much for explaining me this
sure!
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?
no idea
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
ye
Or you could make the joke: -(-x - y) = x + y
what
@@BackToBackSWE it doesn't use '+'.
This is the best explanation I've ever seen! Thanks a lot!!!
sure
This is the ultimate guide to this hell of bits manipulation. Thank you so much.
Tried this question on leetcode and it fails for the test case -1 & 1, any idea how to correct it for this situation?
It only works for positive integers
Yes, this works only for positive intergers. see stackoverflow.com/questions/39113479/infinite-loop-while-adding-two-integers-using-bitwise-operations-in-python-3
However in the aforementioned stackoverflow post, its only explained why the solution fails for negative integers in python; you could probably look at this additionally: leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary:-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently/289784
Where can I find the link for code? Not in description?
The repository is deprecated - we only maintain backtobackswe.com now.
If you had to put a number on it , what do you think is the probability of getting a bit manipulation question on my next interview?
It depends on the company
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
Hi Sir, where can we find the code? I can't find your code on your platform nor in the description. Thank you in advance!
The repository is deprecated - we only maintain backtobackswe.com now
wiah! thats good content
You helped a lot , thank you for making such kind of videos.....
sure
what is the runtime of this algorithm? Leetcode says O(N + M) but I don't understand :(
can't explain rn but saw this, I dont remember the problem too well I'd have to refresh. Rapid fire replying
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)]
nice
Ok, so this works for negative numbers, too, excellent. But maybe someone can explain why it does?!
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?
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.
Awesome video. There is one doubt though. There was one question on CodeChef December challenge www.codechef.com/problems/BINADD where we had to find the number of times this loop gets executed. My question is how many times does the iterations get executed. Or rather after how many iterations does the carry become 0?
I'm not sure
Back To Back SWE + Leetcode + Cracking the Coding Interview = Total Interview prep package
4:00 what i think most of us came for starts here XD
we already know binary sys
edit: 7:25 it was at this moment that i knew i pressed the red button
edit: make videos for the other operations pleeeeeeeeez
Is there any mathematical proof that Any Numbers can be expressed as Addition of numbers in multiple of 2 ??
If there wasn't such a disparity in income I'd suggest you become a teacher instead of a sw engineer! Great break down
ye
just hearing carrys a bunch of times, repeated binary numbers so very ambiguous where they've come from.
You said the code was in the comments I don't see it
The repository is deprecated - we only maintain backtobackswe.com now.
well i faced this question in the interview :( and not the data structures.
That sucks. Where was it?
@@BackToBackSWE At MAQ Software
Again a great video😉
thx
Thanks for the explanation!
But when I implement this logic using Python, testing with negative values will exceed time limit. Do you have any advice to deal with this issue?
Thanks!
not sure
What happens when we have carry in last bit and we left shift. If integer size is not increased we will lose that value.
Code is NOT in the description, feels like clickbait
if i keep going like this one day i will have a comment on each of your video lol
yes
this is really awesome. really loved it gr8 work!!!! all doubts are solved thanks..!!!!
sure
jade smith is that you ?
Commendable !!!Just wow!!!!!!!
thx
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.
Never thought about this logic 😯😯.... Amazing 😍😍
sure
The best teaching that I have seen in my life till now is yours .
thanks
I can't find the code. Where is it?
The repository is deprecated - we only maintain backtobackswe.com now
OMG came from Geeksforgeeks. Thank you so much sir.
sure
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