How to implement arithmetic right shift in C
#define USES_ARITHMETIC_SHR(TYPE) ((TYPE)(-1) >> 1 == (TYPE)(-1))
int asr(int value, int amount) /* Better codegen on some older compilers */
{
return !USES_ARITHMETIC_SHR(int) && value < 0 ? ~(~value >> amount) : value >> amount ;
}
int asr2(int value, int amount) /* Completely portable */
{
return value < 0 ? ~(~value >> amount) : value >> amount ;
}
This code decides whether to just use the builtin >>
operator or not first. You might want to either trust or not trust the preprocessor giving you the same result as the target architecture, but a safe fallback is to not trust it.
Let's explain the value < 0 ? ~(~value >> amount) : value >> amount
part.
- If
value >= 0
then it doesn't matter whether>>
is logical or arithmetic, we can use it. - If
value < 0
then~value
is the bitwise complement which will be a positive number and(~value >> amount)
will be portable (the topamount
number of bits will be cleared, the rest shifted right as expected).
~(~value >> amount)
will flip all the bits back, including flipping the topamount
number of zeroes to ones which is exactly what you want with arithmetic right shifting.
The code assuming USES_ARITHMETIC_SHR(int) == true
compiles with -O2
into:
asr(int, int): // x86-64 GCC 4.4.7
mov eax, edi
mov ecx, esi
sar eax, cl
ret
asr(int, int): // x86-64 Clang 3.4.1
mov cl, sil
sar edi, cl
mov eax, edi
ret
asr(int, int): // ARM GCC 4.5.4
mov r0, r0, asr r1
bx lr
This should be portable but I'm also unsure if it pedantically really is. If you aren't either, you can #define USES_ARITHMETIC_SHR(TYPE) false
or just omit checking it and only check value < 0
. But that results in less optimal code on the some older compilers.
The newest version of the compilers (GCC 8+, Clang 7+) compile both versions, asr
and asr2
to the same, efficient assembly as above, so you can use either versions of the code. Below is how older compilers do with asr2
, a very portable solution.
asr2(int, int): // x86-64 GCC 4.4.7
test edi, edi
js .L8
mov eax, edi
mov ecx, esi
sar eax, cl
ret
.L8:
mov eax, edi
mov ecx, esi
not eax
sar eax, cl
not eax
ret
asr2(int, int): // x86-64 Clang 3.4.1
mov cl, sil
sar edi, cl
mov eax, edi
ret
asr2(int, int): // ARM GCC 4.5.4
cmp r0, #0
mvnlt r0, r0
mvnlt r0, r0, asr r1
movge r0, r0, asr r1
bx lr
sometime early in your runtime you could check the sanity of your assumption
int check_sanity()
{
if (~0ll != ~0ll>>8)
{
return 0; // not sane
}
return 1; // sane
}