2

I need to implement a 32-bit arithmetic right shift from logical shifts, and, or, xor and normal integer arithmetic operations.

I read somewhere the following is supposed to work:

(x>>N)|(((1<<N)-1)<<(32-N))

x is the integer that will be shifted and N is the amount of bits to shift.

This works for negative (msb is 1) numbers but not for positive numbers (msb is 0).

Does anyone know an efficient algorithm that always produces the right result?

phuclv
  • 37,963
  • 15
  • 156
  • 475
user2358122
  • 23
  • 2

2 Answers2

2

You can use this

(x >> N) | (-(x < 0) << (32 - N))

If x is negative then -(x < 0) returns -1, which have a bit pattern of all 1s, assuming 2's complement. -1 << (32 - N) will make a value which has all 1s in the top N bits and 0s in the remaining part. If x is non-negative then the latter part will always be zero, and the result will be the same as a logical shift. Alternatively it can be modified to

(x >> N) | ~(((x < 0) << (32 - N)) - 1)

Note that it won't work for N <= 0 or N >= 32 (since shifting more than the width of type invokes UB) so you should treat those cases specifically if needed

If you're not allowed to use comparison then you can change x < 0 to (unsigned)x >> 31 and get the below equivalent ways

(x >> N) | (-((unsigned)x >> 31) << (32 - N))
(x >> N) | ((~0*(unsigned)x >> 31) << (32 - N))
(x >> N) | ~((((unsigned)x >> 31) << (32 - N)) - 1)
phuclv
  • 37,963
  • 15
  • 156
  • 475
  • Re "Therefore `-1 << (32 - N)` will make a value which has all 1s the top N bit and 0s in the remaining part", which is incorrect for positive numbers, like the OP said. – ikegami Aug 08 '14 at 15:37
  • @ikegami Oops! I forgot that. Fixed – phuclv Aug 08 '14 at 15:49
  • `x < 0`? Is that one of the allowed operators? What do you assume it returns? – ikegami Aug 08 '14 at 17:25
  • @ikegami why not? it's a "normal integer arithmetic" operator. In C/C++ it always returns 0 and 1 – phuclv Aug 08 '14 at 17:28
  • He's probably looking for operators that exist as CPU instructions. As such, it's not an integer arithmetic operator since it's neither integer arithmetic nor an operator. – ikegami Aug 08 '14 at 17:31
  • (Doesn't it return return `true` or `false` in C++?) – ikegami Aug 08 '14 at 17:32
  • @ikegami He's using `<<` and `>>` so assume he's using a C-based language. It's not correct in all those languages but it's easy to convert the values. In C++ [true == 1 and false == 0](http://stackoverflow.com/questions/5189072/c-bool-question) – phuclv Aug 08 '14 at 17:34
  • Re, "He's using `<<` and `>>` so assume he's using a C-based language", That makes no sense. All those operators are present in GW-BASIC, and it's not C based. And in GW-BASIC, `<` returned 0 or -1. Furthermore, `<` doesn't always return 0 or 1 in C-based languages. e.g. They don't in C++ and Perl. That's why I had to ask what assumptions you made. Anyway, there's no reason to prove I didn't. – ikegami Aug 08 '14 at 17:43
  • +1, but your using << on a negative number which is also undefined behaviour. See http://stackoverflow.com/questions/8415895/is-left-and-right-shifting-negative-integers-defined-behavior – qbt937 Nov 17 '14 at 03:51
0

LSR 1:

+---+---+---+---
|   |   |   | ...
+---+---+---+---
   \   \   \   \
    \   \   \  
     \   \   \
+---+---+---+---
| 0 |   |   | ...
+---+---+---+---

ASR 1:

+---+---+---+---
|   |   |   | ...
+---+---+---+---
  |\   \   \   \
  | \   \   \  
  |  \   \   \
+---+---+---+---
|   |   |   | ...
+---+---+---+---

An ASR consists of an LSR plus an OR.

So you want to replicate bit31 N times. The efficient solution is probably an efficient implementation of 

( bit31 ? 0xFFFFFFFF : 0x00000000 ) << ( 32 - N ) )

I've come up with

LSL(SUB(LSR(NOT(X), 31), 1), SUB(32, N))

The whole thing

OR(LSL(SUB(LSR(NOT(X), 31), 1), SUB(32, N)), LSR(X, N))

That doesn't seem very efficient.

ikegami
  • 367,544
  • 15
  • 269
  • 518