18

According to the C / C++ standard (see this link), the >> operator in C and C++ is not necessarily an arithmetic shift for signed numbers. It is up to the compiler implementation whether 0's (logical) or the sign bit (arithmetic) are shifted in as bits are shifted to the right.

Will this code function to ASSERT (fail) at compile time for compilers that implement a logical right shift for signed integers ?

#define COMPILE_TIME_ASSERT(EXP) \
    typedef int CompileTimeAssertType##__LINE__[(EXP) ? 1 : -1]

#define RIGHT_SHIFT_IS_ARITHMETIC \
    ( (((signed int)-1)>>1) == ((signed int)-1) )

// SHR must be arithmetic to use this code
COMPILE_TIME_ASSERT( RIGHT_SHIFT_IS_ARITHMETIC );
Adisak
  • 6,708
  • 38
  • 46
  • 3
    What is your failed compilation going to do for those who have a machine that uses a logical shift? Why is your software not going to be usable on such a machine/compiler? Wouldn't it be better to write the code so it works regardless of whether the right shift of a signed number is arithmetic or logical? – Jonathan Leffler Oct 21 '09 at 06:03
  • 6
    I am using branch-free selection (BFS) through bit twiddling. It requires an arithmetic shift to work. I'm putting the COMPILE_TIME_ASSERT( RIGHT_SHIFT_IS_ARITHMETIC ); in the BFS header. The code needs to use the RIGHT_SHIFT_IS_ARITHMETIC define to select the traditional or the branch-free paths. It can be a massive speedup on the PS3/XBOX360 CPU's to use branch-free code due to branch mispredict penalties. – Adisak Oct 21 '09 at 15:54
  • 1
    BTW, the failed compilation at a compile time assert where the reason is explicitly noted is better than just having the code mysteriously fail... basically it's going to say that these routines aren't supported by this compiler (or CPU). – Adisak Oct 21 '09 at 15:56
  • Adisak: be sure to profile the improvement you get from that mask-add trick -- on the int unit I found it to be only sometimes an improvement over the plain old cmp/bge, depending on how well the compiler managed to interleave stuff around it. It wasn't the unmitigated massive win that `fsel` is. – Crashworks Oct 21 '09 at 17:06
  • @Crashworks: That is a universal truth: make sure your "optimizations" run faster. I have tested all my BFS optimizations to make sure they run considerably faster on all 3 platforms we support. Some of them did not make the cut... for example, Mike Acton suggested using branchfree selection rather than variable shift for the CELL (PS3) CPU on his cellperformance.com site because the variable shift is microcoded. I tried that out and it was considerably slower than just using the microcoded variable shift instruction. – Adisak Oct 21 '09 at 17:18
  • Ha! I tried that same change on the Xenon and came to the same conclusion. – Crashworks Oct 21 '09 at 18:24
  • @Crashworks: I just found your question on that and answered it: http://stackoverflow.com/questions/539836/emulating-variable-bit-shift-using-only-constant-shifts/1603803#1603803 – Adisak Oct 21 '09 at 22:21
  • 1
    Alternate suggestion: If you can't find a good way to perform this test at compile-time, there's nothing wrong with doing a quick run-time test at the top of main(), and crashing with an informative diagnostic/advice if the run-time test didn't give the results you wanted. It's not quite as good as a compile-time error, but since it can't be missed in testing, it avoids the possibility of accidentally shipping with incorrect code enabled. – Jeremy Friesner Jan 25 '19 at 16:25
  • @Adisak you might be interested in this answer https://stackoverflow.com/questions/76495063/how-can-i-reliably-perform-an-arithmetic-shift-right-in-c/76495064#76495064 – Kevin H. Patterson Jun 17 '23 at 08:05

3 Answers3

6

Looks good to me! You can also set the compiler to emit an assembly file (or load the compiled program in the debugger) and look at which opcode it emits for signed int i; i >> 1;, but that's not automatic like your solution.

If you ever find a compiler that does not implement arithmetic right shift of a signed number, I'd like to hear about it.

Crashworks
  • 40,496
  • 12
  • 101
  • 170
  • Yeah, I basically want it automatic... looking at the opcodes is not reasonable expectation for this requirement because I am using it in a library that other teams may use on various platforms. – Adisak Oct 20 '09 at 22:50
  • The compiler for [UNISYS 2200 system](http://stackoverflow.com/a/12277974/995714) uses logical right shift for signed types. "The result of the expression E1 >> E2 is that E1 (interpreted as a bit pattern) is shifted to the right E2 bit positions. The right shift is *logical (that is, zero-filled on the left) even if the E1 expression is a signed integer type*." http://public.support.unisys.com/2200/docs/cp14.0/pdf/78310422-011.pdf – phuclv Aug 17 '15 at 05:29
  • [Signed right shift: which compiler use logical shift](https://stackoverflow.com/q/6487918/995714) – phuclv Jan 25 '19 at 16:19
1

Why assert? If your compiler's shift operator doesn't suit your needs, you could gracefully remedy the situation by sign-extending the result. Also, sometimes run-time is good enough. After all, the compiler's optimizer can make compile-time out of run-time:

template <typename Number>
inline Number shift_logical_right(Number value, size_t bits)
{
    static const bool shift_is_arithmetic = (Number(-1) >> 1) == Number(-1);
    const bool negative = value < 0;
    value >>= bits;
    if (!shift_is_arithmetic && negative) // sign extend
        value |= -(Number(1) << (sizeof(Number) * 8 - bits));
}

The static const bool can be evaluated at compile time, so if shift_is_arithmetic is guaranteed to be true, every compiler worth its salt will eliminate the whole if clause and the construction of const bool negative as dead code.

Note: code is adapted from Mono's encode_sleb128 function: here.

Update

If you really want to abort compilation on machines without arithmetic shift, you're still better off not relying on the preprocessor. You can use static_assert (or BOOST_STATIC_ASSERT):

static_assert((Number(-1) >> 1) == Number(-1), "Arithmetic shift unsupported.");
marton78
  • 3,899
  • 2
  • 27
  • 38
  • There is a lot of code (for example, Branch-Free-Selection using Masks) that only makes sense to use on compilers with arithmetic signed shift. Gracefully emulating an arithmetic shift on them would probably be significantly slower than the original code, therefore eliminating the "optimization". – Adisak Sep 17 '12 at 15:55
  • Fair enough. Nevertheless, my second point is still valid: don't rely on the preprocessor. See update. – marton78 Sep 17 '12 at 16:48
  • 1
    static_assert() is C++11x and we can't use boost. But the check I was doing doesn't rely on the preprocessor, I could just do the following but it is much harder to read and understand than the example I wrote: `typedef int CompileTimeAssertArithmeticShift[( (((signed int)-1)>>1) == ((signed int)-1) ) ? 1 : -1];` – Adisak Sep 17 '12 at 22:44
0

From your various comments, you talk about using this cross-platform. Make sure that your compilers guarantee that when they compile for a platform, their compile-time operators will behave the same as run-time ones.

An example of differing behavior can be found with floating point numbers. Is your compiler doing its constant-expression math in single, double, or extended precision if you're casting back to int? Such as

constexpr int a = 41;
constexpr int b = (a / 7.5);

What I am saying is, you should make sure your compilers guarantee the same behavior during run-time as compile-time when you're working across so many different architectures.

It is entirely possible that a compiler might sign-extend internally but not generate the intended opcode(s) on the target. The only way to be sure is to test at run-time or look at the assembly output.

It's not the end of the world to look at assembly output...How many different platforms are there? Since this is so performance-critical just do the "work" of looking at 1-3 lines of assembler output for 5 different architectures. It isn't as if you have to dive through an entire assembly output (usually!) to find your line. It's very, very easy to do.

phuclv
  • 37,963
  • 15
  • 156
  • 475
std''OrgnlDave
  • 3,912
  • 1
  • 25
  • 34