Do an arithmetic left shift of x by n bits (C)

-4

Me and my group of 4 people are both completely blanking on how to correctly do an arithmetic left shift of an int x, by an amount of n bits.

It is a for a homework problem on bit manipulation for C. We are not allowed to use loops, if statements, or any operations over 15. I've attached the code given below. Also, the simple solution x << n does not work, even though I'm sure we are missing something obvious. If anyone could help or provide guidance, it would be much appreciated.

    /* 
    * arithLeftShift - Do an arithmetic left shift of x by n bits.
    *   Can assume that 0 <= n <= 31
    *   Examples: arithLeftShift(0x87654321,4) = 0xF6543218
    *   Legal ops: ~ & ^ | + << >> !
    *   Max ops: 15
    *   Rating: 3
    */
    int arithLeftShift(int x, int n) {
   return 0;
   }

Current error message:

Test arithLeftShift(-2147483648[0x80000000],1[0x1]) failed...
...Gives 0[0x0]. Should be -2147483648[0x80000000
c
bit-manipulation
asked on Stack Overflow Oct 2, 2019 by flunky2k

2 Answers

0

Actually, It is not arithmetic left shift.It's your arithLeftShift with your sign bit needn't a left shift. And the high bits needed to be shifted to the low position, It looks like a cycle shift.

#include<stdio.h>
int main()
{
    arithLeftShift(0x87654321,4);
}
int arithLeftShift(int x,int n)
{
    int temp,i;  //define two auto variables,
    i=x>>(32-n);//i for x's high n bits.
    temp=x<<n;//temp for x left shift n bits

    if(x>0)//sign bit is 0,
    {
        x=temp+i;
        x=x>0?x:x^0x80000000;//change the x sign bit is 0;
    }
    else
    {//when you do right shift, there will be different with different compliers and your x.
        if(i>0){//This means when you do right shift, 0 be inserted into high bits.
        x=temp+i;
        }
        else
        {
          i=(0x80000000>>(32-n));
          x=temp+i;
        }
        x=x>0?~(x^(~0x80000000)):x;//change the x sign bit is 1
        printf("%x\n",x);
    }
}
answered on Stack Overflow Oct 2, 2019 by youpen • edited Oct 2, 2019 by youpen
0

Your ask seems to be to "Rotate" the integer "Left", "n" number of times but retain the "Sign Bit"(MSB) if set.

One solution would be......

#include <stdio.h>   
#define INT_BITS 32  

int arithLeftShift(int x, int n) {
  int res;
  res = (x << n | (x >> (INT_BITS - n) & ~(~0 << n))) | x & (~0 << (INT_BITS - 1));
  return res;
}

int main(){

  int x = 0x87654321;
  int n = 4;

  printf("0x%x\n",arithLeftShift(x,n));

}

Explanation:

  • (x << n)

Left shift x, n times - the last n bits are zero.

(x >> (INT_BITS - n) & ~(~0 << n))

Right shift x (INT_BITS - n) times to put the first n bits at the correct position and "AND" it with ~(~0 << n) to set the upper bits to zero.This will take care of "sign extension", if any.

(x << n | (x >> (INT_BITS - n) & ~(~0 << n)))

"OR" them to perform the "Rotate Left" operation.

  • x & (~0 << (INT_BITS - 1)

Left shift "-1", 31 times and "AND" it with x to check if the MSB of x is set.

(x << n | (x >> (INT_BITS - n) & ~(~0 << n))) | x & (~0 << (INT_BITS - 1))

Finally "OR" the above expressions to get your answer.

answered on Stack Overflow Oct 2, 2019 by Lily AB

User contributions licensed under CC BY-SA 3.0