CODEWITHSUNDEEP
cbit-manipulationbit-shift
calebeja9
calebeja9

Reputation: 53

logical shift in c understanding

I'm currently trying to understand how this logical shift works. Given the formula:

int logicalShift(int x, int n){
    int mask = x >> 31 << 31 >> n << 1;
    return mask^ (x>>n);
}

Test run of x = 0x87654321 and n = 4. gave logicalShift(x,n) = 0x08765432

Here, I know that x in binary is 1000 0111 0110 0101 0100 0011 0010 0001 and following the mask process,

x >> 31 is 0000 0000 0000 0000 0000 0000 0000 0001

and << 31 to that is 1000 0000 0000 0000 0000 0000 0000 0000

and >> n to that is 0000 1000 0000 0000 0000 0000 0000 0000

and << 1 to that is 0001 0000 0000 0000 0000 0000 0000 0000.

doing mask^ (x>>n) means doing XOR to 0001 0000 0000 0000 0000 0000 0000 0000 with 0000 1000 0111 0110 0101 0100 0011 0010 which results in 0001 1000 0111 0110 0101 0100 0011 0010 which would be 0x18765432.

Have I done the shifting wrong?

Upvotes: 1

Views: 1282

Answers (3)

Antti Haapala -- Слава Україні
Antti Haapala -- Слава Україні

Reputation: 133849

This excerpt is wrong:

int logicalShift(int x, int n){
    int mask = x >> 31 << 31 >> n << 1;
    return mask^ (x>>n);
}

The behaviour of x >> 31 when x is negative is implementation-defined. The << 31 with negative value or if it changes the sign bit has undefined behaviour. It will work as if it did logical shift under very strict assumptions:

  • the width of int is 32 bits
  • the signed integers have 2's complement as their internal representation
  • that the behaviour of right-shift of negative numbers does arithmetic right shift,
  • that the behaviour of left-shift of negative numbers is defined as if the 2's complement representation shifted left logically.

Such does not follow from the C standard. However, it would behave as expected on any GCC target platform where int is 32-bits wide as GCC specifies the 3 last ones as true.

This code is wrong because to do a proper logical shift, one should to use unsigned values. However, to get these back to a signed value is tricky - not that it would usually be needed.

This function has completely defined behaviour for logical right shift given that the value of n is within the limits (non-negative and less than the width of x in bits):

unsigned int logicalShift(unsigned int x, int n) {
    return x >> n;
}

As it does one expression only, we notice that using a function for such an operation is not needed.

Upvotes: 2

Achal
Achal

Reputation: 11921

x >> 31 is 0000 0000 0000 0000 0000 0000 0000 0001 No, its wrong. your x is signed integer and num is 0x87654321 that means last 31st bit is 1 or set, so when you do right shifting that sign bit get copied, that result x as 1111 1111 1111 1111 1111 1111 1111 1111

To get expected output take num as unsigned type.

int logicalShift(unsigned int x, int n){
   /* some code */
}

Note that its implementation dependent as If your processor supports arithmetic right shifting then last bit(sign bit) gets copied into remaining bytes and if its a logical right shifting then it won't.

Upvotes: 0

user743382
user743382

Reputation:

Yes, you've done the shifting wrong. When >>'s left operand is a signed integer, compilers will typically perform an arithmetic right shift, not a logical right shift. This is hinted at in the function name: if >> performed a logical right shift, it could just return x >> n directly. The point of the function is to implement a logical right shift by using arithmetic right shift.

What arithmetic right shift means is that when right-shifting, the left bits are not filled with zeroes, but are filled with whatever the left-most bit (the sign bit) was. Therefore:

x >> 31 is 0000 0000 0000 0000 0000 0000 0000 0001

x >> 31 is actually 1111 1111 1111 1111 1111 1111 1111 1111.

Upvotes: 1

Related Questions