Understanding the right shift operator with bit shifting

Question

I am having difficulty understanding the right shift operator. I understand the left shift.Say we have a no

int n = 11; which is 1011

Now if we left shift it n << 1 The result is

int a = n << 1 ; so a = 10110; (simply add a 0 to the end)

This makes sense

Now Right shift is where I am having difficulty

int a = n >> 1

I would think the answer is 01011 (add a 0 to the front) which would be 1011 again but instead its 101. My question is how did we loose the last digit.

Update: My reasoning for this might be suppose an int is 8 bit in that case we will have int8 n = 1011 => which is 00001011 so when we right shift by 1 it exceeds 8 bit int by 1 so the last bit is dropped and it becomes 0000101 ? Is this understanding correct ?

Answer 1

Seems like you have a misunderstanding of how shifts work.

Shifting does not add zero's left or right. You can't just add digits, there are only so many bits. Lets take your number, the decimal number 11.

int n = 11; which is 1011

This is true, but only half the story. See, numbers have a fixed size in your CPU. For integers, thats 32 bits, but to make it easier, lets assume 8 bit numbers. Your 11 looks like this:

+-+-+-+-+-+-+-+-+
|0|0|0|0|1|0|1|1|
+-+-+-+-+-+-+-+-+

It has 8 bits. Always. Now lets do a left-shift by 1:

 +-+-+-+-+-+-+-+-+
0|0|0|0|1|0|1|1| |
 +-+-+-+-+-+-+-+-+

After you shifted, the first bit got "shifted out". There is no space to store that bit. Also, the last bit is "empty", we can't store "emptyness". There is only one or zero. Instead, we "shift in" zero's. So you end up with

+-+-+-+-+-+-+-+-+
|0|0|0|1|0|1|1|0|
+-+-+-+-+-+-+-+-+

On a right-shift its the other way around. We start with 11 again:

+-+-+-+-+-+-+-+-+
|0|0|0|0|1|0|1|1|
+-+-+-+-+-+-+-+-+

and shift right by 1:

+-+-+-+-+-+-+-+-+
| |0|0|0|0|1|0|1|1
+-+-+-+-+-+-+-+-+

Again, every bit got shifted right by 1. On the left there is an empty bit which, as previously, just becomes zero. On the right, the one got shifted out and there is no space to store it. It is just lost. Our final number is:

+-+-+-+-+-+-+-+-+
|0|0|0|0|0|1|0|1|
+-+-+-+-+-+-+-+-+

---

Above is true for unsigned numbers, also called a logical right-shift. On a two's complement system, for signed numbers, it uses the so-called arithmetic right-shift, which instead of shifting in zero-bits, it shifts in sign-bits. I.e. if the number is negative, hence the most significant bit is one, it shifts in one's, otherwise it shifts in zero's.

Answer 2

1011 will be 101 after right shift. right most bit got removed from 1011.

111110101 when right shifted by 3 gives 111110, removing the bolded bits 111110101

Answer 3

There are several ways to look at it.

First, integer numeric types (in C, C++, Java, C#) have a fixed number of bits. So 11 is actually (assuming the rare 8 bit int for readability):

 00001101 (8 digits)

Shifting left one bit

000011010 (9 digits?)

But since our integer can manage only 8 bits, the leftmost bit falls off.

00011010 (8 digits)

Same happens with 32 bit integers: the leftmost bit falls off.

The same happens with the right shift: the bit on the right falls off. If the original is:

00011010 (8 digits)

Then adding a bit on the left creates a 9 bit value, which is unsupported. Instead, the added zero pushes all bits one place to the right, and the rightmost bit falls off, and the result is

00001101 (8 digits)

Another way to look at it is like multiplication and division. In decimals, when we multiply by 10, a zero is added on the right. Left shift is like multiplication, but for binary. When we divide by 10, then we remove the rightmost digit and put it in a fraction part. With a positive binary and right shift it is the same, we simply lose the fraction.

Note that with negative numbers things are more complicated in C++. For example, left shifting a negative is undefined

Answer 4

Let's say we have a number (we'll make it simple, say 00010000) and we want to bit shift it left, it will look like this:

00010000 << 1 = 00100000

We have taken a number, and put the value of every column in the column 1 space to its left (because 1 is the number we put on the other operand of the bit shift).

With me so far? good.

Now, what does a right shift do? Well, it does the opposite It puts the value of every column in the column x spaces to its right. For example:

00010000 >> 1 = 00001000

A few more more advanced examples:

01010101 << 1 = 10101010
01010101 >> 1 = 00101010

11111111 << 2 = 11111100
11111111 >> 2 = 00111111

NOTE: Bit shifts will cut off any bits that get shifted over the boundary of the data, like in the example of 11111111, any bits that fall over the edge after the shift get lost.

Answer 5

You didn't "lose" the last digit. You just weren't shifting the value you thought you were.

You started out with n = 0b1011. You shifted that to the left by one bit and stored the result into a, leaving n unchanged. You then shifted n (still with value 0b1011) to the right and got 0b0101.

Had you shifted a to the right rather than n, you would have seen the result you expected.