0

[Part of a HW question]

Assume 2's complement, 32bit word-length. Only signed int and constants 0 through 0xFF allowed. I've been asked to implement a logical right shift by "n" bits (0 <= n <= 31) using ONLY the operators: ! ~ & ^ | + << >>

I figured I could store and clear the sign bit, perform the shift, and replace the stored sign bit in its new location.

I would like to implement the operation "31 - n" (w/out using the "-" operator) to find the appropriate location for the stored sign bit post shift.

If n were positive, I could use the expression: "31 + (~n + 1)", but I don't believe this will work in the case when n = 0.

Here's what I have so far:

int logicalShift(int x, int n) {
/* Store & clear sign bit, perform shift, and replace stored sign bit
   in new location */  
int bit = (x >> 31) & 1; // Store most significant bit
x &= ~(1 << 31); // Clear most significant bit
x = x >> n; // Shift by n
x &= ~((~bit) << (31 - n)); // Replace MSbit in new location

return x;
}

Any help and/or hints are appreciated.

sgoldburg
  • 31
  • 7
  • The last operation should probably be an or, not an and. – MikeMB Oct 09 '16 at 22:22
  • Why don't you just make an arithmetic shift and clear the high bits? – MikeMB Oct 09 '16 at 22:24
  • 1
    If you are ok to code in current standard C, or any previous versions of standard C, you can just cast it to unsigned int, then shift, then cast it back. Or go straight old-school and write inline assembly. – user3528438 Oct 09 '16 at 22:46
  • @MikeMB Can't use any constants larger than 0xFF. Would this sort of mask be possible with that restriction? – sgoldburg Oct 09 '16 at 22:49
  • the limitation on operators makes it tricky but still you can do `return (x+0u)>>n;` – user3528438 Oct 09 '16 at 22:49
  • @user3528438 Can't use any form of casting. – sgoldburg Oct 09 '16 at 22:49
  • no, no casting (no casting operators), no large constants, standard C99 code, try it here: https://ideone.com/eHEoBL – user3528438 Oct 09 '16 at 22:53
  • @user3528438 Thank you. That does work. Unfortunately, the only data type I can use is signed int. Tried not to go into all the restrictions in the post ... – sgoldburg Oct 09 '16 at 23:04
  • It may be easier to look at it in a different way. Rather than removing the sign bit to prevent the sign propagation from the arithmetic shift, why don't you just shift it and then remove all the shifted in bits instead. Surely there's an easy way to create a mask of the bits to keep. – Jeff Mercado Oct 09 '16 at 23:19
  • 1
    You might get better answers on electronics stack exchange despite being a programming question. Software engineers are going to tell you how to do this in software but you are trying to model hardware! – dave Oct 09 '16 at 23:20
  • 2
    `31 + (~n + 1)` actually works when `n=0`. – user3528438 Oct 09 '16 at 23:44
  • @user3528438 You're right, I was overthinking it. Thanks again. – sgoldburg Oct 10 '16 at 00:00
  • Even if one assumes "2's complement,", `1 << 31` is _still_ undefined behavior and a compiler that uses 2's complement `int` may still not create the hoped for code. Such tricks are better suited for assembly code than C. Since OP answered in the question (a no-no on stack-overflow, just make your own answer,) nothing left but to DV. – chux - Reinstate Monica Oct 10 '16 at 02:53
  • @chux Sorry, guess I missed that in the guidelines ... I'll move it to an answer. – sgoldburg Oct 10 '16 at 03:28
  • @chux is the bit representation of `1 << 31` (what we're after here) undefined ? – sgoldburg Oct 10 '16 at 03:43
  • @sgoldburg Yes, for 32-bit `int`, `1 << 31` is UB (§6.5.7 11 4). Code this and someday in the future when code fails, you may recall this. Use unsigned math like ``1u << 31` – chux - Reinstate Monica Oct 10 '16 at 03:47

2 Answers2

1

[EDIT: Solved]

Thanks to everyone for the help. ~n + 1 works to negate n in this situation, including for the case n = 0 (where it returns 0 as desired). Functional code is below (by no means the most elegant solution). Utility operations borrowed from: How do you set, clear, and toggle a single bit?

int logicalShift(int x, int n) {
/* Store & clear sign bit, perform shift, and replace stored sign bit
   in new location */
int bit = (x >> 31) & 1; // Store most significant bit
x &= ~(1 << 31); // Clear most significant bit
x = x >> n; // Shift by n
x ^= ((~bit + 1) ^ x) & (1 << (31 + (~n + 1))); // Replace MSbit in new location

return x;
}
Community
  • 1
  • 1
sgoldburg
  • 31
  • 7
0

A simple solution is

int logicalShift(int x, int n) {
    return (x >> n) ^ (((x & 0x80000000) >> n) << 1);
}

Sadly, using the constant 0x80000000 is forbidden. We could calculate it as 1 << 31 (ignoring undefined behavior in C) or, to save on instruction, calculate 31 - n as n ^ 31 and then use the following somewhat more contrived method:

int logicalShift(int x, int n) {
    int b = 1 << (n ^ 31);
    return b ^ ((x >> n) + b);
}
Falk Hüffner
  • 4,942
  • 19
  • 25