Arithmetic Right Shift 1101 >> 2, wrong solution in Cracking the Coding Interview?

Question

(For reference: Table on p.89 of Cracking the Coding Interview by Gayle Laakmann McDowell)

The solution for 1101 >> 2 is 0011. Is the book's answer wrong? Because from what I've read online and from this stackoverflow post, I thought it should be 1111.

My reasoning is because >> is an arithmetic right shift where you shift with the most significant bit (the left most bit because it preserves negative numbers). Am I understanding this wrong?

Answer 1

You shift all the bits and the extra bits fall off the end. So your bits are marching right and zeros march in from the left to take their places:

 zeros live here   1101
                  0110 and the 1 falls off the end
                 0011 and the 0 falls off the end

Answer 2

The author did not clarify this, but apparently it is not intended to be an arithmetic shift...

Answer 3

You didn't tag the language but in C shifting on a signed value is implementation defined behavior, so if the book is talking about signed type, obviously it defines right shift as logical. Shifting on unsigned type always result in a logical shift. In most other C-like languages like Java >> is a logical shift

Another possibility is that the book is omitting the top bits, because you can't have a native 4-bit type in any languages (unless you're talking about bitset in C++ or similar). But storing only 4 bits in a byte will leave the high bits zero, so shifting right always zero out the bits regardless of the right shift type

Answer 4

The author meant shifts shift the decimal pointer two to the right. When applying this 01 "rolls of the end" and you this leaves you with 0011.

This matches the expected result on page 89 in the "Cracking the Coding interview" book when referring to the 6th edition.

In C++ you can write it like this:

#include <bitset>
#include <iostream>
using namespace std;

void main()
{
    int a = 13; // 1101
    bitset<4> x(a);
    cout << x << '\n';

    bitset<4> y(x >> 2);    
    cout << y << '\n';
}

output:

1101
0011

Answer 5

technically right-shift of a signed negative number is implementation-dependent, you have to provide context.