I came to youtube understand bit manipulation after reading first chapter of your book.... And boom I have the author explaining me herself... Thank you soo much Gayle😀
It has to be said Gayle is a superwoman. Looking at what she was wearing it appears as though she did this series of videos in the same day and that’s just amazing to me that she can offer this instruction like that.
You need the basics of binary to understand. It will help to learn binary conversion to hexa-decimal and base-10. Also learning "signed" binary, will help with understanding the twos complement which I think she explained quite well. You'll get there!
For 2's complement, you don't have to do that much work. Just keep same all the bits till you encounter first 1 from right to left. After first 1 complement each bit. For example, 010100 -> xxx100 ->101100. :D
Subtracting one and then inverting the bits also works - each of these methods have utility depending on the environment. For example, they could simplify a more complex bit twiddling, or have dedicated hardware. Thanks for sharing this alternative.
What you need to keep in mind is: if you shift too much to the left, you end up with communism. Too much to the right you've got a Facist state. Neither are good.
The part you mentioned was regarding getting the bit at the 'i' th position. To get that bit we need to do a Bitwise AND with the binary number which has 1 at the 'i'th position. So to create that binary number we take 1, which is represented as 00000001, shifting the 1 to 'i'th position, (which gives 00100000 in the video, actually depends on i) and do a bitwise AND with the binary representation of the given number. If the result is a zero then you know that the 'i'th bit is zero else its a 1.
At 2:45, she says "So let's think about this. What number would we have to add to 00 100 10 to get 1 000 000 0." I know about 2s complement, but I donot get why we need to get 1 000 000 0?
Hey :) Just so you can see why its -12: 1 1 1 1 0 1 0 0 in artihmetic base 10 numbers works out to be: -128 + 64 + 32 + 16 + 0 + 4 + 0 + 0 = -12 When the signed bit is a 1, the value is -128, then you add left to right as usual. Hope this helps!
explanation of concept is very good but only one thing is missing i.e some real world problem, just introduce some real world problem without solution, You can post solution in some other video.. ;)
snlgrg your concern is fair, altough I would also encourage you to dive more into the conceptual approach just for fun. Real world applications will always be there waiting 😀
you guys provide a great explanation, but I still think you need to go a little slower so the people can understand it much better and please try to explain videos in depth a little bit ;)
This is solid, but I've been somewhat impressed how tricky some of the more advanced bit manipulation problems on HackerRank can get even for someone who's known the basics for years. Sure, you know XOR, but do you REALLY know XOR....
Very wordy and much technical jargon. Hard to follow for someone new to the topic. The curse of knowledge means that the more you know, the easier it is to talk like an expert and alienate non-experts. The way to explain this bit manipulation information to beginners is to keep it in very simple wording. Such is understanding your audience and who is receiving the information. If that audience is people who are new to the topic, they will be lost in translation.
Whatta hell?? How ignorant I have been! I've never had to deal with bit operations until now, but I have always presumed that you just use the exact same bits (except the first sign bit) to differentiate between positive or negative numbers. Like say the number 18 in base 10 is 00010010, and -18 is 10010010. Why is this a bad idea, someone?
Thanks a bunch for the answer! I've been reading up on different signed representations after my first post, and turns out that some architectures actually do use the "magnitude representation", but they are outdated, so my hunch was not totally wrong. Looks like all modern x86/x84 machines uses "two's complement".
@Mohanad Darwish , sure! Cracking the Coding Interview, Cracking the tech career , CLRS , Algorithm Design by Springer, some Russian book and I'm not sure about the others... Hope that helps
This is where the distinction between signed and unsigned integers comes in. If the data-type we're talking about is an unsigned 8-bit integer, then 10000101 is 133. If it's a signed 8-bit integer, then 10000101 is -123. Unsigned 8-bit integers can be in the range 0 to 255. Signed 8-bit integers are in the range -128 to 127. Both can hold 256 different values, but the signed ones are centered around zero.
When is this practical? You know I saw this used in some Google code for a particular object in Android SDK a while back, and it looked like the developer was trying to be clever in squeezing every last bit of efficiency possible out of his/her algorithm.. however if you extended their object in a certain way (which was for a popular use-case at the time) the algorithm then broke for certain situations causing a very elusive bug.. I wish I remember the specifics, think it may have been one of the support libraries.. I do remember it was a pain to track down and I had to override alot of the base methods because of it.. it scared me off of ever using this technique in commercial code..
Have you never looked at the source code for the java.util packages? The collections defined in that package are going to be used in pretty much every Java application on the planet. They're full of bit operations. They're a fast and efficient way of doing a lot of basic mathematics that would otherwise cause unnecessary slowdown.
@@KingOfAceZ1 alot of CompSci students today don't understand that the stuff they use is built on these very operations that they think no longer serve any practical purpose.
@@KingOfAceZ1 I programmed a digital lock in assembly using an 8bit pic microcontroller and you are correct we are indeed standing on the shoulders of giants. The people that are the most guilty are probably web devs, they seem like they have a package for everything...
Than. You random lady U just explained in a few seconds what my teacher couldn’t over the course of a few lectures (maybe that’s cause i wasn’t listening 🌚)
@8:12 when Gayle is explaining how to "clear the ith bit", she mentions that all you have to do is invert your existing binary number, then AND it with the inverted number. But if you pay attention, you will see that she doesn't invert the two 1's near the right side of the binary number. Does anyone have any idea why she may have done it this way?
Go to leetcode and filter the problems by bit manipulation, I recommend then sorting by most frequent so you are more likely to find an accompanying video tutorial on youtube if you get stuck.
Right, which is why she carries it. Same as in decimal where there is not single symbol for 10. We still describe the condition for carrying a number as two digits in the same place adding up to 10 or more even though there is no "10" symbol, or what is represented as "A" in hexadecimal.
Good video but wish it spent more time explaining why we use two's compliment vs one's compliment and the difference. I got stuck on that for a little bit.
The simplest reason that 2's complement is preferred over 1's complement is that with 1's complement you end up with two zeros, a + and a - zero which can lead to ambiguity within the hardware-software implementation of the adders. Also, 2's complement has the effect that when you add any two signed numbers you will get the correct result for both positives and negatives whereas with 1's complement in some situations the result will be off by 1 due to the two zeros that are produced by 1's complement.
Depends on if it is logical or arithmetic. Logical will push the last bit before the sign bit. Arithmetic will multiply the number by two and keep the sign bit.
It's a random number that she uses for the purpose of just showing how to add them. So she could have used any other numbers, I got confused by it at first as well.
101 is 1x2^2+0x2^1+1x2^0 = 5 It just like how 105 = 1×10^2+0×10^1+5×10^0 But in binary you have 2 possible number (0 & 1) while in decimal you have 10 possible numbers (0 to 9) and the power is just the index of the number starting at 0 from the right side incrementing as you move to the left so in binary 0 = 0x2^0 = 0 in decimal 1 = 1×2^0 = 1 in d 10 = 1×2^1+0×2^0 = 2 in d 11 = 1×2^1+1×2^1=3 in d 100 = 1×2^2+0×2^1+0×2^0 = 4 in decimal Anything multiplied by 0 is 0 so we can skip that So 100 = 2^2 = 4 583 = 2^9+2^6+2^2+2^1+2^0 So these will be ones and everything in between will be zeros so 583 = 1001000111
Or maybe he wanted to express his gratitude- give a compliment ? Don't forget there are different types of intellgience, you might lack social/emotional intelligence when you call out people for no good reason...
She's pretty fucking smart. She has multiple graduate degrees from top tech schools, a career of working at the top tech companies, is a writer and a teacher. Look at her linkedin for godsakes! Her genotype is superior to ours in every way, caveman.
hope some one help me with my question minute 2:45, i completely understand how we inverse the number, but why arbitrary 10 00 00 00(128)? from e where does it come that?
For example after +127 (01111111) we get -(0) which is 1000000. Although that zero is basically 128 as unsigned 8-bit number, it becomes the first zero before we get to the first negative number, -127 (10000001).
This is where the distinction between singed and unsigned integers comes in. If the data-type we're talking about is an unsigned 8-bit integer, then 10000101 is 133. If it's a signed 8-bit integer, then 10000101 is -123. Unsigned 8-bit integers can be in the range 0 to 255. Signed 8-bit integers are in the range -128 to 127. Both can hold 256 different values, but the signed ones are centered around zero.
I'm late, but i want to add that the point of representing signed numbers this way, is that we can use the same adition operation on both signed and unsigned types and still get the correct result. So we can use the same adition circuit to add signed and unsigned integers, we can also implement subtraction by adding A + (-B) and that also works for signed and unsigned numbers, it's a really convenient and powerfull practice
still a little 'bit' lost ;)))
this is not a good explanation video
@Juan2003gtr your GTR needs a new transmission Juan, ve te a la chingada
Yep better watch xorpd assembly lecture
Boomm drop da maik
@@pwn0x80 Thanks. I just subbed xorpd. I tried to read some code that had a lot of bit shifting.
It's all the bits and pieces into one video, represented very interestingly. Thank you!
Great video, but the masking section was done too quickly... You needed a bit more in depth examples for each type.
I came to youtube understand bit manipulation after reading first chapter of your book.... And boom I have the author explaining me herself... Thank you soo much Gayle😀
It has to be said Gayle is a superwoman. Looking at what she was wearing it appears as though she did this series of videos in the same day and that’s just amazing to me that she can offer this instruction like that.
I'm still trying to compute all of this information. It's a bit overwhelming.
wah wah whaaaaa
shift to another things and then come back to continue w the video.
It's a "bit" too much I agree
You need the basics of binary to understand. It will help to learn binary conversion to hexa-decimal and base-10.
Also learning "signed" binary, will help with understanding the twos complement which I think she explained quite well.
You'll get there!
@@SkeleCrafteronYT @Ivan Leon I think the person was making a joke (a 'bit' overwhelming).
If anyone tries this in Python, be careful because shifting 1 "i times" will not provide the correct bit mask for the "i th" bit: 1
let your counting start from 0 down to the left
the best video talks about bit operation i've ever found! Thank you so much!
After watching several videos of others, I finally landed on the right one, which is precisely what I was looking for. Thanks a lot.
This REALLY helped clarify the shifting and mask business for me. Thanks!
I'm a *bit* interested
just a little bit
@@esjihn Not a tad bit though.
naughtyy!!
nice
For 2's complement, you don't have to do that much work. Just keep same all the bits till you encounter first 1 from right to left. After first 1 complement each bit. For example, 010100 -> xxx100 ->101100. :D
but that's a slower algorithm than inverting the bits and adding one.
I think it's faster on paper but slower for the computer
Subtracting one and then inverting the bits also works - each of these methods have utility depending on the environment. For example, they could simplify a more complex bit twiddling, or have dedicated hardware. Thanks for sharing this alternative.
you helped me get much more clear with the bit manipulation things, thanks!
I got a little lost at 7:23 when she starts talking about shifting the number to the left by i spots
yeah exactly she didnt bother to explain why original number % (random) mask should not be zero in the first place ,,,
What you need to keep in mind is: if you shift too much to the left, you end up with communism. Too much to the right you've got a Facist state. Neither are good.
The part you mentioned was regarding getting the bit at the 'i' th position. To get that bit we need to do a Bitwise AND with the binary number which has 1 at the 'i'th position.
So to create that binary number we take 1, which is represented as 00000001, shifting the 1 to 'i'th position, (which gives 00100000 in the video, actually depends on i) and do a bitwise AND with the binary representation of the given number.
If the result is a zero then you know that the 'i'th bit is zero else its a 1.
don't you mean a little BIT lost?
@@gulammohiddin5747 Hi Gulam, so you always start with one and then start shifting?
Excellent video. It feels good to finally understand something about Bit Manipulation
At 2:45, she says "So let's think about this. What number would we have to add to 00 100 10 to get 1 000 000 0." I know about 2s complement, but I donot get why we need to get 1 000 000 0?
She understands English, Spanish, Russian and Korean given the books on her desk?
Number:23
Left shift:Number*2=23*2=46
Right Shift:Number/2=23/2=11
Hey :) Just so you can see why its -12:
1 1 1 1 0 1 0 0 in artihmetic base 10 numbers works out to be:
-128 + 64 + 32 + 16 + 0 + 4 + 0 + 0 = -12
When the signed bit is a 1, the value is -128, then you add left to right as usual. Hope this helps!
explanation of concept is very good but only one thing is missing i.e some real world problem, just introduce some real world problem without solution, You can post solution in some other video.. ;)
go to their website and sign up and you'll have examples, really worth it, just signed up a few days ago, probably the best free help ive found
Completely agree. Been doing the 30 day code challenge to better myself.
snlgrg your concern is fair, altough I would also encourage you to dive more into the conceptual approach just for fun. Real world applications will always be there waiting 😀
check out the geeks for geek
you guys provide a great explanation, but I still think you need to go a little slower so the people can understand it much better and please try to explain videos in depth a little bit ;)
9:00 The only thing I understood 100%
So that's about what? 2 maybe 5% of the whole?
hahahaha
Lol this tickled me so
1. convert 123 to binary. 2 Invert bits, and then add 1. Why do we add one? 4:22
I think 1(0000001) is the number you need to add to your inverted number so you can get the negative version of 123
Jump to the 5:20 if you want to know the difference between logical and arithmetic right shift.
This is solid, but I've been somewhat impressed how tricky some of the more advanced bit manipulation problems on HackerRank can get even for someone who's known the basics for years. Sure, you know XOR, but do you REALLY know XOR....
This lady is lowkey one of the biggest g's in coding lol
great video LOVING this channel
8:19 for big picture of getting, setting, and clearing
Very wordy and much technical jargon. Hard to follow for someone new to the topic.
The curse of knowledge means that the more you know, the easier it is to talk like an expert and
alienate non-experts. The way to explain this bit manipulation information to beginners is to keep it in very simple wording.
Such is understanding your audience and who is receiving the information. If that audience is people who are new to the topic, they will be lost in translation.
Very clear! Would have been great if it is shown with coding examples.
Whatta hell?? How ignorant I have been! I've never had to deal with bit operations until now, but I have always presumed that you just use the exact same bits (except the first sign bit) to differentiate between positive or negative numbers. Like say the number 18 in base 10 is 00010010, and -18 is 10010010. Why is this a bad idea, someone?
Thanks a bunch for the answer! I've been reading up on different signed representations after my first post, and turns out that some architectures actually do use the "magnitude representation", but they are outdated, so my hunch was not totally wrong. Looks like all modern x86/x84 machines uses "two's complement".
Not just those, but 19 of 20 others are thereabouts as well.
@@sunnyhours84 yeah it is not a stupid idea, in your own project you can totally do somethings like that!
Never mind, got it. It's just an example of how to add up 2 digits. Can't believe i had to watch the video twice to get it.
Which software are you using to explain things ?
Thanks.. Yours lectures have been very helpful!!
Couldn't you just use x^1
No, it wil invert nth bit instead of clearing
Did anyone got interested about the pile of books behind her and if they are well known or just decoration?
They are indeed well known books! She has authored two of them, the other books are like Bible: CLRS, Algo design from Springer , etc.
Aishwarya Ramesh if you are free can you share their names? If you u know them or can read it from the video :)
@Mohanad Darwish , sure!
Cracking the Coding Interview, Cracking the tech career , CLRS , Algorithm Design by Springer, some Russian book and I'm not sure about the others... Hope that helps
The legend herself!!
Regarding clearing the ith bit, can't we do x xor (1
does she show us how to actually add "1" to the binary inverse of the positive binary representation? like its a pretty big step she just glosses over
so how can you tell the difference of -123 and 133 in binary? they both are 10000101
This is where the distinction between signed and unsigned integers comes in. If the data-type we're talking about is an unsigned 8-bit integer, then 10000101 is 133. If it's a signed 8-bit integer, then 10000101 is -123.
Unsigned 8-bit integers can be in the range 0 to 255.
Signed 8-bit integers are in the range -128 to 127.
Both can hold 256 different values, but the signed ones are centered around zero.
@@APaleDot clearest explanation I've seen on this in a while.
When is this practical? You know I saw this used in some Google code for a particular object in Android SDK a while back, and it looked like the developer was trying to be clever in squeezing every last bit of efficiency possible out of his/her algorithm.. however if you extended their object in a certain way (which was for a popular use-case at the time) the algorithm then broke for certain situations causing a very elusive bug.. I wish I remember the specifics, think it may have been one of the support libraries.. I do remember it was a pain to track down and I had to override alot of the base methods because of it.. it scared me off of ever using this technique in commercial code..
Have you never looked at the source code for the java.util packages? The collections defined in that package are going to be used in pretty much every Java application on the planet. They're full of bit operations. They're a fast and efficient way of doing a lot of basic mathematics that would otherwise cause unnecessary slowdown.
embedded systems? you know, electronics that you can't just download a magical sdk for?
you're standing on the shoulders of giants, lol.
@@KingOfAceZ1 alot of CompSci students today don't understand that the stuff they use is built on these very operations that they think no longer serve any practical purpose.
@@KingOfAceZ1 I programmed a digital lock in assembly using an 8bit pic microcontroller and you are correct we are indeed standing on the shoulders of giants. The people that are the most guilty are probably web devs, they seem like they have a package for everything...
You introduced the concept of "inverse" without even defining it. What does inverse mean??
Sounds like Rebecca Black is narrating this.
for the twos component you said we just add the inverse so why did you put a 1 if there's already a 1?
Atleast the voice in this video is clear
Nice Short and Clear.
Good way to explain bits!
In the last example @8:20, could you not shift a 0 instead of inverting a 1? So (0
Than. You random lady
U just explained in a few seconds what my teacher couldn’t over the course of a few lectures (maybe that’s cause i wasn’t listening 🌚)
1 minute into the video do you know where she got 637? Thanks a lot if you can explain.
@@Saykey20111 She was just showing you how to add up numbers
Excellent video, thank you.
m a bit overwhelmed after seeing this video
@8:12 when Gayle is explaining how to "clear the ith bit", she mentions that all you have to do is invert your existing binary number, then AND it with the inverted number. But if you pay attention, you will see that she doesn't invert the two 1's near the right side of the binary number. Does anyone have any idea why she may have done it this way?
OhhOmni I had the same question. Hopefully someone can chime in with some insight
"AND it with a mask with a 1 everywhere else but that one spot". She then said to get this by inverting the previous mask, not the existing number.
Great content with good explanation. Thank you👍
Are there coding challenges (excercises) that deal with bit manipulation? To nail the foundations.
Go to leetcode and filter the problems by bit manipulation, I recommend then sorting by most frequent so you are more likely to find an accompanying video tutorial on youtube if you get stuck.
7:20 is the !=0 necessary? Wouldn't just returning the result also work? If it's a 1, 1 != 0 is 1. If it's a 0, 0 != is 0.
In binary there is no 2, as being explained 1:38 instead it's 1+1=10 (from this result 0 is placed while 1 is carried to next calculation...
Right, which is why she carries it. Same as in decimal where there is not single symbol for 10. We still describe the condition for carrying a number as two digits in the same place adding up to 10 or more even though there is no "10" symbol, or what is represented as "A" in hexadecimal.
that -18 from 18 was damn cool
in clearing the bit, the invert bits are wrong at the 3& 4th place?
one of the best video I've ever seen ..
really appreciate your work
big thumbs up 👍
Огромное спасибо за столь хорошее объяснение материала!
Good video but wish it spent more time explaining why we use two's compliment vs one's compliment and the difference. I got stuck on that for a little bit.
The simplest reason that 2's complement is preferred over 1's complement is that with 1's complement you end up with two zeros, a + and a - zero which can lead to ambiguity within the hardware-software implementation of the adders. Also, 2's complement has the effect that when you add any two signed numbers you will get the correct result for both positives and negatives whereas with 1's complement in some situations the result will be off by 1 due to the two zeros that are produced by 1's complement.
Masterclass !
i like the way she says hi
Gail is a fantastic teacher!
7:23 I don't understand this notation.
(x&(1
ok, i think `x` is the byte we're evaluating, and `
Bit masking and bit manipulation is where we programmers separate the boys from the men. Or girls from the women.
what if a 1 sexually identifies as a 0
life gets a bit complicated
cant even miss gender numbers anymore can we
where did you get that 637. You to explain for those who are not gifted too.
It's a random number that she chose because it nicely demonstrates "carrying the one"
Hello so when i want to use the arithmeric shift to the right for example on 1011 then i get 1101 and by 0101 i get 0010?
Everyone around here is a bit too good at making puns.
what about when you shift a negative number to the left ?
Depends on if it is logical or arithmetic. Logical will push the last bit before the sign bit. Arithmetic will multiply the number by two and keep the sign bit.
this is really good.
The Hackerrank link doesn't work any longer.
what she told from 3:38 ? little confusing. can anybody explain ? why to add 1 to both of those ?
good video) after watching this i took a certificate at HackerRank
Oh lord, I've been doing this to "clear a bit" in one of my programs
x &= (0
Now my left ear knows about bit manipulation
greate video, but where did you get the numbers 637 and 011.
It's a random number that she uses for the purpose of just showing how to add them. So she could have used any other numbers, I got confused by it at first as well.
That "manipulation" square wave got me distracted.
What is "Bitpul Ian Man Tio" ?
Bit manipulation :-)
thanks very good explanation
how the hell is 8 bit used does the computer have the right to only use 8 at one time or how?
good video but it is so densely packed, it is not good for beginner to learn at such rapid pace.
how is arithmetic shift of -23 12 i does not work bit wise right??
how do you flip the bit in python? "~" in python does not flip the bits
Thank you very helpful..🌹
great quality
wait, what did i miss ? Binär: 101 isn´t 583 ?!
101 is 1x2^2+0x2^1+1x2^0 = 5
It just like how 105 = 1×10^2+0×10^1+5×10^0
But in binary you have 2 possible number (0 & 1)
while in decimal you have 10 possible numbers (0 to 9) and the power is just the index of the number starting at 0 from the right side incrementing as you move to the left
so in binary
0 = 0x2^0 = 0 in decimal
1 = 1×2^0 = 1 in d
10 = 1×2^1+0×2^0 = 2 in d
11 = 1×2^1+1×2^1=3 in d
100 = 1×2^2+0×2^1+0×2^0 = 4 in decimal
Anything multiplied by 0 is 0 so we can skip that
So 100 = 2^2 = 4
583 = 2^9+2^6+2^2+2^1+2^0
So these will be ones and everything in between will be zeros
so 583 = 1001000111
A little confused at the masks
A bit confused
Pretty amazing
I will fail the interview if asked bitwise operations now lol
Me to
They don't even teach this shit in my college.
Dx D
You don’t take discrete math or low level systems?
Really thank you so much for your clear explanation!
waiting for more videos (Y)
What are the books on the table???
How are you so smart?
Sergeeg Hard work.
you must be pretty dumb if you think shes SO SMART lmao
Or maybe he wanted to express his gratitude- give a compliment ? Don't forget there are different types of intellgience, you might lack social/emotional intelligence when you call out people for no good reason...
She's pretty fucking smart. She has multiple graduate degrees from top tech schools, a career of working at the top tech companies, is a writer and a teacher. Look at her linkedin for godsakes!
Her genotype is superior to ours in every way, caveman.
go flip more burgers, you pathetic fuck lol
She reminds me of Jan from The Office
hope some one help me with my question minute 2:45, i completely understand how we inverse the number, but why arbitrary 10 00 00 00(128)? from e where does it come that?
For example after +127 (01111111) we get -(0) which is 1000000. Although that zero is basically 128 as unsigned 8-bit number, it becomes the first zero before we get to the first negative number, -127 (10000001).
I watch whole video for masking, and ended up not understanding it, total
waste
very good vid
I feel a Bit better now ;)
do i really need to know this for tech internships?
Daniel Ro Yes
How do you tell the difference between -123 and 133?
This is where the distinction between singed and unsigned integers comes in. If the data-type we're talking about is an unsigned 8-bit integer, then 10000101 is 133. If it's a signed 8-bit integer, then 10000101 is -123.
Unsigned 8-bit integers can be in the range 0 to 255.
Signed 8-bit integers are in the range -128 to 127.
Both can hold 256 different values, but the signed ones are centered around zero.
I'm late, but i want to add that the point of representing signed numbers this way, is that we can use the same adition operation on both signed and unsigned types and still get the correct result. So we can use the same adition circuit to add signed and unsigned integers, we can also implement subtraction by adding A + (-B) and that also works for signed and unsigned numbers, it's a really convenient and powerfull practice