CODEWITHSUNDEEP
c++
MSalters
MSalters

Reputation: 179799

Elegant way to express shift left OR right in template

I currently have a template function which, depending on its template parameters A and B, may shift a value either left or right:

template <int A, int B> void f(X) {
// ...
if (A >= B)
{
  SetValue(X << (A-B));
}
else // (A < B)
{
  SetValue(X >> (B-A));
}

When I instantiate the template for A<B, I get a warning for a negative shift right on the (unreachable) first branch, and else I get a warning for a negative shift left on the first branch. Our codebase is warning-free so this isn't acceptable. Is there a concise, readable alternative to these two shift statements?

Similar questions (e.g. Dynamically shift left OR right) don't have this spurious warning as the shift distance is a runtime variable there.

Upvotes: 6

Views: 1521

Answers (12)

MSalters
MSalters

Reputation: 179799

To answer my own question : using C++17, it's now easy.

template <int A, int B> void f(X) {
if constexpr (A >= B)
// ^^^^^^^^^
{
  SetValue(X << (A-B));
}
else // (A < B)
{
  SetValue(X >> (B-A));
}

The branch where the shift is negative will be discarded.

Upvotes: 0

davmac
davmac

Reputation: 20631

Cast the result of (A-B) and (B-A) to unsigned, and additionally mask (bitwise-and) it with (sizeof(int) - 1). This clears the warning for GCC 5.5 and 6.3. For more recent versions of GCC no warning is generated.

template <int A, int B> void f(int X) {
  // ...
  if (A >= B)
  {
    SetValue(X << ((unsigned)(A-B) & (sizeof(int) - 1)));
  }
  else // (A < B)
  {
    SetValue(X >> ((unsigned)(B-A) & (sizeof(int) - 1)));
  }
}

Note to address the various comments about undefined behaviour: the only sense in which this proposed solution might cause undefined behaviour is by performing a shift of an amount greater than the bit-width of the operand. However, this is guarded by the comparison; assuming that the difference between A and B is a safe shift count, which is implied in the question, then if (A >= B) ensures that that only a shift with that amount actually executes. The other branch of the if statement is not executed and so does not perform a shift and cannot produce undefined behaviour from the shift (although if it were executed, it certainly would do so).

A couple of commenters have made an assertion that the branch which is not executed can still cause undefined behaviour. I am somewhat at a loss as to how such a miscomprehension could occur. Consider the following code:

int *a = nullptr;

if (a != nullptr) {
    *a = 4;
}

Now, if dereference of a null pointer causes undefined behaviour even when it is not executed, the guard condition becomes useless. This is clearly not the case. The above code is perfectly fine; it assigns a a value of nullptr, and doesn't then dereference a, due to the guard. Although such obvious examples (with the assignment to null immediately followed by a check for null) do not tend to occur in real code, the "guarded dereference" in general is a common idiom. It certainly does not by itself produce undefined behaviour if the pointer checked actually is null; that's why the guard is useful.

Upvotes: 4

jcoder
jcoder

Reputation: 30035

How about something like this :-

#include <iostream>

template <int A, int B, bool D> class shift
{
};

template <int A, int B> class shift<A, B, false>
{
public:
    static int result(int x) {return x << (B-A);}
};

template <int A, int B> class shift<A, B, true>
{
public:
    static int result(int x) {return x >> (A-B);}
};


template <int A, int B> int f(int x)
{
    return shift<A, B, (A>B)>::result(x);
}

int main()
{
    std::cout << f<1, 2>(10) << "\n";
    std::cout << f<2, 1>(10) << "\n";
}

Upvotes: 0

TemplateRex
TemplateRex

Reputation: 70526

This is what I use in my draughts engine which heavily uses bitboards for its board representation

namespace detail {

enum { Left, Right };

template<typename, std::size_t>
struct Shift;

// partial specialization for bitwise shift-left
template<std::size_t N>
struct Shift<Left, N>
{
        template<typename T>
        T operator()(T x) const
        {
                return x << N;
        }
};

// partial specialization for bitwise shift-right
template<std::size_t N>
struct Shift<Right, N>
{
        template<typename T>
        T operator()(T x) const
        {
                return x >> N;
        }
};

} // namespace detail

template<int N>
struct Shift
{
        template<typename T>
        T operator()(T x)
        {            
            return N >= 0 ? detail::Shift<Left, N>()(x) : detail::Shift<Right, -N>()(x);
        }
};

template <int A, int B> 
void f(int x)
{
     SetValue(Shift<A-B>()(x));
}

You can do something similar for ShiftAssign (<<= and >>=).

Upvotes: 1

Mark B
Mark B

Reputation: 96241

I think a fairly minor change would simply be to zero out the non-executed shift with a multiply. The compiler can still do all the work at compile time:

template <int A, int B> void f(X) {
// ...
if (A >= B)
{
  SetValue(X << ((A < B) * (A-B)));
}
else // (A < B)
{
  SetValue(X >> ((A >= B) * (B-A)));
}

I believe a cleaner approach may be to dispatch to a true/false specialized template that knows how to shift the proper direction.

Upvotes: 0

jrok
jrok

Reputation: 55395

template< int A, int B > void f(X)
{
    std::function< int(int, int) > shift =
        A < B
        ? [](int X, int N) { return X << N; }
        : [](int X, int N) { return X >> N; }

    SetValue( shift( X, std::max(A,B) - std::min(A,B) ) );
}

Upvotes: 0

MSalters
MSalters

Reputation: 179799

davmac's comment ("use &0x1F") was the right idea, except for the assumed maximum shift width. That was easily fixed:

template <int A, int B> void f(X) {
// ...
if (A >= B)
{
  SetValue(X << abs(A-B));
}
else // (A < B)
{
  SetValue(X >> abs(B-A));
}

Upvotes: 1

piwi
piwi

Reputation: 5336

You could put the shift operations in seperate structures and use std::conditional in C++11:

template <typename A, typename B, typename X>
struct ShiftRight
{
    static void shift() { SetValue(X >> (A - B)); }
};

template <typename A, typename B, typename X>
struct ShiftLeft
{
    static void shift() { SetValue(X << (A - B)); }
};

template <typename A, typename B, typename X>
void f()
{
    typedef typename std::conditional<A >= B, ShiftLeft<A, B, X>, ShiftRight<A, B, X>>::type ShiftType;

    ShiftType::shift();
}

Upvotes: 0

James Kanze
James Kanze

Reputation: 153909

The most obvious is to forward to a function taking an additional argument:

template <bool Cond> struct Discrim {};

template <int A, int B>
void f( Discrim<false> )
{
    SetValue( X, (A - B) );
}

template <int A, int B>
void f( Discrim<true> )
{
    SetValue( X, (B - A) );
}

template <int A, int B>
void f()
{
    f( Discrim< (A < B) >() );
}

(Use of such a Discrim class template is one of the simpler meta-programming techniques.)

Upvotes: 3

Pete Becker
Pete Becker

Reputation: 76245

Off the top of my head:

template <int A, int B> struct whatever {
    static void f() {
        SetValue(X << (A - B));
    }
};

template <int A, int B, bool reversed> helper : whatever<A, B> {
};

template <int A, int B, true> : helper whatever<B, A> {
};

template <int A, int B> do_it : helper<A, B, B < A> {
};

template <int A, int B> void f() {
    return do_it<A, B>::f();
}

Upvotes: 0

Jack Aidley
Jack Aidley

Reputation: 20107

You could add a new template, and specialise it appropriately, e.g.:

template<bool b> int Shift(int i, int a, int b);

template<true> int Shift(int i, int a, int b) { return i << (a-b); }
template<false> int Shift(int i, int a, int b) { return i >> (b-a); }

And then invoke it as Shift<(A >= B)>(X, A, B). That should work.

Upvotes: 0

ForEveR
ForEveR

Reputation: 55887

With C++11 or boost.

template<int A, int B>
void f_impl(typename std::enable_if<(A >= B)>::type* = 0)
{
   // first case
}

template<int A, int B>
void f_impl(typename std::enable_if<(A < B)>::type* = 0)
{
   // second case
}

template<int A, int B>
void f()
{
   f_impl<A, B>();
}

Upvotes: 6

Related Questions