[MUSIC]. In this video we're going to talk about shifting operations for both unsigned and signed integers and see how that how, how we need to do some sign extension for sign values. Let's get started with just the case of unsigned integers. What I'm showing here is both the, Left shift operation, and the Right shift operation, in[UNKNOWN] and you'll notice we used the double less than sign, and the double greater than sign to indicate those. But don't think of them as less than or greater than. Those are just symbols for those shift operators. we just use those because they kind of look like a move to the left and a move to the right. So, when we say x shifted to the left by y, what we mean is we're going to move the bit patter of x to the left by that many positions the value of y. Let's take a look at this example here, here's the number six. represented in eight bits and we're going to shift to the left by 3. So, in this case the y value is 3. And what we'd expect to have happened, is that those bits would move over by three positions, okay? And you'll notice that high order three bits, the most significant bits. we're going to kind of lose, they're just going to drop off the end. And we're going to have a hole left over on the right of, three bits that we need to fill. And we're just going to fill that with zeroes. Okay? Now, the right shift is very analogous. We're just going to move things over by two. In this case we've lost the one and the zero, the two least significant bits. And we have a hole of two on the left to fill in. And we're just going to put zeros in there. Okay, so that's the basic left-shift and right-shift operator. Let's take a look at another example. But before we do that actually, let me just take a look at these values here. I said that this was the number six. This turns out to be the number 48. And this is the number one. So, when we did a left shift by 3, what we did was essentially multiply that 6 by the value 8. How did we get 8? That's 2 to the 3rd power. the number of bits were moving to the left. Okay? so we can use shifts to often do multiplications quickly, by, because these are much simpler operations to implement in hardware than a multiplier would be. but of course, we can only do powers of two. Similarly a shift to the right is a division operation, in this case we took the six and divided it by two to the two or four and we got one as a result. Now you see in fact we probably wanted one point five but we cant represent fractional values, so it got rounded down to one okay. Let's take a look at this other example with the number 242. represented in our eight bits when we shift to left by three we're going to multiply that by eight, so we're going to get this value, which is actually the number 144. Well that's not 242. Multiplied by eight. Well, that's a much larger number and way larger than the 255 which is our maximum value for an 8-bit unsigned integer. So, we're, we're, we have an overflow here, so we're going to get a value that doesn't really make any sense. So, this tells us that. You know, when we're thinking about doing multiplications using shift. We've got to check the number before we shift it, to make sure that the result will in fact fit in the, in, in the eight bits that we have, or whatever number of bit word we have. But, if we do a divide by four, or a right shift by two we would expect to get a result of 60.5 and in fact that is the value that we get. This is 60. Of course it got rounded, it's not 60.5 so we have that rounding issue again. Okay, let's take a look now at a signed integers. It's a little bit different situation. here I'm showing a signed integer that's equivalent to the number 98. and we're going to left shift it by 3 multiply by again this is way too big a number. we're going to get a result that is equivalent to 16 which is wrong of course because we should have got 784. Alright, so now let's try the right shift, divide by four. right shift by two and we would want to see the number 24.5 of course we can't get the 24, we can't get the 24.5 we're just going to get 24. The rounded version of 24.5 okay, now, in in dealing with signed integers, we have to think about that sign pit that we didn't have to think about before. So in, we also have another kind of right shift called an arithmetic shift, where instead of filling in those two bits with zeroes, we're going to fill in those two bits with a copy. Of the signed bit, the most significant bit. In this case that turns out to be exactly the same thing so we see any difference. But let's take a look at what happens with a negative number. so down here we have an example with the number minus 94 and again multiplying it by eight. Doing that left shift by three, is going to yield too negative a number and we're going to end up with a result of 16, which is just clearly wrong again. and again that's because now we've had an underflow, we had too negative a number as a result. When we divide by 4 by shifting to the right by 2. We would want the result to be minus 23.5. But if we just fill in with zeros, as we do for our logical shift then we're going to get a result of 40, which is also clearly wrong. It's not even negative. we've totally lost that sign bit. And that's why we have arithmetic shifts. In this case, again we're going to copy that most significant bit. Into those bit positions, so instead of ending up with a positive number we still have a negative value. In this case we have a negative value minus 24 which isn't the minus 23.5 we would want but again it's a rounded version of that okay it's minus 24. And one thing to keep in mind is in C things are undefined if we shift try to shift by a negative number or by something larger than the word size. The result is undefined and we could expect to just get junk as a result of that. Alright let's see how the shift operations can be used for more interesting things though than just doing basic multiplication and division by a power of two. Here I'm showing how we can extract the second most significant byte of an integer using Shift and Masking. All right, so, the example we're going to start with is this 32-bit pattern. And we want the second most significant byte. That's the one with the red box around it. And we can get that to all the way over to the right by shifting that value by 16 to the right. Okay? So, now we've moved that byte over to the low order eight bits. And you notice we padded with zeros on the far left end. Our next operation is what is called a masking operation, were going to use this bit pattern which is all zeros except for ones in the low or the byte. That's represented by the value 0xFF in hexadecimal. So, all 1s in the, in the low order byte. And when we mask that, or AND, do a logical bit-wise AND with our our shifted value, we will just get the result of that first byte, because ANDing, remember, with a 1 the result is just the other value. While ANDing with a zero, the results will always be zero. And we'll just end up with all zeros everywhere else, okay. So, that masking operation is very powerful that way. We can also use shifting and masking to extract the sign bit on an integer. For example, if we just wanted to know if it was positive or negative. What we can do is take the, the signed integer x, shift it to the right by 31 bits, so that the signed bit ends up in the low order bit position. And then AND it with the number one, which just has a one in that one position. Right, about low order bit. And everything else will get cleared out to zero, so that's how we can extract the sign bit and our result will either be zero if the sign bit was zero or a one if the sign bit was one. And that makes it easy for us to test at that number. what's positive or negative. We can also do conditional as Boolean expressions, remember, let's assume that the Boolean value is either zero or one for now, not anything else. In C, I can do a conditional with an if statement. I can write if x meaning if x is true, then assign the value of y to a,and if x is false, the else clause assign the value of z to a. In C I can also write it in this notation using a question mark, so that i can fit it all into an assignment statement. This says a is equal to either y or z, depending on the value of x. If x is one then it will be y. If x is zero it will be the value z and we use that question mark and colon to delineate those. Okay, so that's how we can see how we can use these conditionals using shift operations. What you'll see down here is two expressions. One for the if part of the clause and the other for the else part of the clause, and lets look at the one on the. left first. You'll notice that what I'm doing is shifting x first to the left by 31 and then to the right by 31. Well, that doesn't seem to make much sense it's kind of doing, should be ending up back where we started but in fact we don't. Because when we shift to the left by 31, we're losing 31 bits off the end. And then when we shift back the right we're doing an arithmetic shift that will copy that most significant bit all the way down through all 32 bits. So, our result will be, if we started with x of 0, we'll end up with all zeros, and if we started with an x of equal to 1, we shifted that 1 lowered bit all the way over to the left. And then arithmetically shifted back it over to the right, filling in behind it with all 1s. So, we'll either have a vector that's all zeros or all ones. And when we and that with y and it's all zeros, we'll just come up with a bunch of zeros, and that'll be it. And if they're all ones, we'll just have the value of y. On the other side, we're just doing the complementary thing by first complementing x and then doing that shift to the left and shift to the right. So, now we'll end up with z effects was 1 to begin with was 0 to begin with and all 0's effects was 1. Okay? Then the addition operator will just combine those values and one of them will be 0, so we'll just end up with the other one, and that's how we get y or z. Into the value, into the variable a. Okay, that might be a little convoluted. You might want to spend some time looking at that. but sometimes you'll see expressions like this in a C program and it's important to understand where they came from. Alright, so that sign extension is really important and so let's take a look at that in a little bit more detail. What we're showing here is a value of x represented in w bits and we're converting it into a value of x into something larger then w bits. Let's say we're going from 32 bits to 64, what we're going to do is copy the 31 low order bits just directly down into the larger representation. But then the most significant bit we will copy throughout the upper 32 bits and we do that to keep the number positive. If it was originally positive or negative if it was originally negative. Okay, so lets take a look at some sign extension examples here I'm showing a short int that is representative in 16 bits. Okay, and then were going to cast it into a 32 bit int. So, we're going to go from short int to int. And what we'll see is for the number 12345, it's represented in 16 bits with that pattern, and then when we cast it into 32 bits, we're just sign extending that 0 sign bit into all the upper 16 bits. Of the larger word. For a negative value, if we use negative 12345 it's represented by this bit pattern. You can tell it's a negative number because the higher order bit is a one and when we sign extend it into the larger representation of 60, of 32 bits, we copy that one throughout those upper 16 bits. Okay? And so sign extension is used both when we're doing arithmetic shifts to the right as well as when we're casting a value into a larger bit path.