-1

Can you please explain the below lines, with some good examples.

A left arithmetic shift by n is equivalent to multiplying by 2n (provided the value does not overflow).

And:

A right arithmetic shift by n of a two's complement value is equivalent to dividing by 2n and rounding toward negative infinity. If the binary number is treated as ones' complement, then the same right-shift operation results in division by 2n and rounding toward zero.

unwind
  • 391,730
  • 64
  • 469
  • 606
AGeek
  • 5,165
  • 16
  • 56
  • 72
  • 1
    Also, I'm not sure where you got this quote from, but a left arithmetic shift by n is equivalent to multiplying by 2^n (*not* 2n). Similarly for right arithmetic shift. – Chris Schmich May 10 '10 at 06:55
  • 2
    I added the awesomeness that is tags, since this question really deserved it. – unwind May 10 '10 at 07:11

3 Answers3

3

I will explain what happens in a base that we're more familiar with: 10.

In base 10, let's say you have a number N=123. Now, you "shift" this number to the left k=3 positions, filling the emptied digits with 0. So you get X=123000.

Note that X = N * 10k.

The case with base 2 is analogous.

 Example 1 (base 10)   |  Example 2 (base 2)
                       |
 N        =    123     |  N       =   110101 (53 in base 10)
 k        =      3     |  k       =        2 (in base 10)
 N << k   = 123000     |  N << k  = 11010100 (212 in base 10)
                       |
 10^k     =   1000     |  2^k     =      100 (in base 2; 4 in base 10)
 N * 10^k = 123000     |  N * 2^k = 11010100 (53 * 4 = 212 in base 10)
                       |

The case with right shift is simply a mirror of the process, and is also analogous in base 10. For example, if I have 123456 in base 10, and I "shift" right 3 positions, I get 123. This is 123456 / 1000 (integer division), where 1000 = 103.

polygenelubricants
  • 376,812
  • 128
  • 561
  • 623
  • Any Good website or document, on Problems on Bit Manipulations.... Need it for good understanding of it.. – AGeek May 10 '10 at 14:09
  • Right shift becomes more interesting when you look at negative numbers. The sign bit is extended, and you end up with the weird-looking behavior of `-1 >> n` being equal to -1 but `1 >> n` being equal to 0 (for any positive `n`). – tomlogic May 10 '10 at 16:37
1

http://en.wikipedia.org/wiki/Arithmetic_shift

zaf
  • 22,776
  • 12
  • 65
  • 95
  • Well I am reading from wikipedia onlyy.. But i am thinking of few examples, in which these conditions are met.. Hope you mite can help out.. – AGeek May 10 '10 at 07:02
0

It's easy to create your own examples.

Consider five which is 101 in binary. Left shift it once and you get 1010 which is binary for ten. Do it again and you get 10100 which is twenty and so on..

Amarghosh
  • 58,710
  • 11
  • 92
  • 121