Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why arithmetic shift halfs a number only in SOME incidents?

Tags:

c#

bit-shift

Hey, I'm self-learning about bitwise, and I saw somewhere in the internet that arithmetic shift (>>) by one halfs a number. I wanted to test it:

44 >> 1 returns 22, ok
22 >> 1 returns 11, ok
11 >> 1 returns 5, and not 5.5, why?

Another Example:

255 >> 1 returns 127
127 >> 1 returns 63 and not 63.5, why?

Thanks.

like image 349
Alon Gubkin Avatar asked Feb 25 '10 16:02

Alon Gubkin


People also ask

What is the purpose of arithmetic right shift?

It is frequently stated that arithmetic right shifts are equivalent to division by a (positive, integral) power of the radix (e.g., a division by a power of 2 for binary numbers), and hence that division by a power of the radix can be optimized by implementing it as an arithmetic right shift.

How do arithmetic shifts work?

To multiply a number, an arithmetic shift moves all the digits in the binary number along to the left and fills the gaps after the shift with 0: to multiply by two, all digits shift one place to the left. to multiply by four, all digits shift two places to the left.

What is the difference between right shift and arithmetic right shift?

Logical right shift means shifting the bits to the right and MSB(most significant bit) becomes 0. Example: Logical right shift of number 1 0 1 1 0 1 0 1 is 0 1 0 1 1 0 1 0. Arithmetic right shift means shifting the bits to the right and MSB(most significant bit) is same as in the original number.


2 Answers

The bit shift operator doesn't actually divide by 2. Instead, it moves the bits of the number to the right by the number of positions given on the right hand side. For example:

00101100 = 44
00010110 = 44 >> 1 = 22

Notice how the bits in the second line are the same as the line above, merely shifted one place to the right. Now look at the second example:

00001011 = 11
00000101 = 11 >> 1 = 5

This is exactly the same operation as before. However, the result of 5 is due to the fact that the last bit is shifted to the right and disappears, creating the result 5. Because of this behavior, the right-shift operator will generally be equivalent to dividing by two and then throwing away any remainder or decimal portion.

like image 136
JSBձոգչ Avatar answered Sep 25 '22 12:09

JSBձոգչ


11 in binary is 1011

11 >> 1 

means you shift your binary representation to the right by one step.

1011 >> 1 = 101

Then you have 101 in binary which is 1*1 + 0*2 + 1*4 = 5.
If you had done 11 >> 2 you would have as a result 10 in binary i.e. 2 (1*2 + 0*1).

Shifting by 1 to the right transforms sum(A_i*2^i) [i=0..n] in sum(A_(i+1)*2^i) [i=0..n-1] that's why if your number is even (i.e. A_0 = 0) it is divided by two. (sorry for the customised LateX syntax... :))

like image 44
pierroz Avatar answered Sep 25 '22 12:09

pierroz