Perform logical shift using arithmetic shift opera

问题:

This question already has an answer here:

• Implementing Logical Right Shift in C 8 answers

Right now I am reading the book Computer Systems : Programmer Perspective.

One problem in the book says to perform a logical right shift on a signed integer, I can't figure out how to start on this.

The following is the actual question from the book:

Fill in code for the following C functions.

• Function srl performs a logical right shift using an arithmetic right shift (given by value xsra), followed by other operations not including right shifts or division.

• Function sra performs an arithmetic right shift using a logical right shift (given by value xsrl), followed by other operations not including right shifts or division.

You may use the computation 8*sizeof(int) to determine w, the number of bits in data type int. The shift amount k can range from 0 to w − 1.

unsigned srl(unsigned x, int k) {
    /* Perform shift arithmetically */
    unsigned xsra = (int) x >> k;
    .
    .
    .
}

int sra(int x, int k) {
    /* Perform shift logically */
    int xsrl = (unsigned) x >> k; 
    .
    .
    .
}

I hope you understand now the question.

回答1:

I won't give you a complete answer as this is apparently homework, but I'll give you some hints to help you work it out for yourself:

• for a logical right shift of N bits you need to clear the top N bits of the result after arithmetic shifting

• you can clear bits in a value by applying an appropriate mask, typically using a bitwise AND or XOR

• to clear the top N bits of a value you need a mask with N 0s and remaining bits 1

• you can generate a suitable mask using left shift by W - N bits, where W is the number of bits in a word (which you can calculate as W = sizeof(int) * CHAR_BIT;)

E.g. for a logical right shift by 2

value              = 10001010
value >>= 2        = 11100010     // arithmetic right shift

mask               = 00111111     // mask has top 2 bits set to 0

value & mask       = 00100010     // apply mask to get logical right shift

The trickiest part is generating the mask, but if you think about left shifts applied so a suitable value, perhaps followed by one further bitwise operation, you should soon see a fairly simple solution.

回答2:

It took me little time to create the mask as suggested by Paul. But I created it as follows.

First I left shifted 1 as follows

1 << (sizeof(int)*8-k);

If I consider k to be 10 and INT size as 32 I will get following mask

   00000000010000000000000000000000 ( 1 at 23 rd position 32 - 10 = 22 )

Then add it with -1 (0xffffffff)

   00000000010000000000000000000000
 + 11111111111111111111111111111111
 +++++++++++++++++++++++++++++++++++

   00000000001111111111111111111111 --> required mask with first 10 bits set to 

Anding with the result of arithmetic shift will give logical shift result.

Following is the C code

unsigned srl(unsigned x, int k) {
/* Perform shift arithmetically */
        unsigned xsra = (int) x >> k;
    int mask = (1 << (sizeof(int)*8-k)) + -1;
    int result = xsra & mask;
}

And It works.