Skip to content

Instantly share code, notes, and snippets.

@pabigot pabigot/rotate.cc
Created Nov 19, 2013

Embed
What would you like to do?
C++11 template function to perform integer rotations without invoking undefined behavior. See http://blog.regehr.org/archives/1063
/* See http://blog.regehr.org/archives/1063
*/
#include <type_traits>
#include <cstdint>
#include <limits>
#include <typeinfo>
#ifndef ARGTYPE
#define ARGTYPE uint32_t
#endif /* ARGTYPE */
using argtype = ARGTYPE;
template <typename T>
T
rotl (T v, unsigned int b)
{
static_assert(std::is_integral<T>::value, "rotate of non-integral type");
static_assert(! std::is_signed<T>::value, "rotate of signed type");
constexpr unsigned int num_bits {std::numeric_limits<T>::digits};
static_assert(0 == (num_bits & (num_bits - 1)), "rotate value bit length not power of two");
constexpr unsigned int count_mask {num_bits - 1};
const unsigned int mb {b & count_mask};
using promoted_type = typename std::common_type<int, T>::type;
using unsigned_promoted_type = typename std::make_unsigned<promoted_type>::type;
return ((unsigned_promoted_type{v} << mb)
| (unsigned_promoted_type{v} >> (-mb & count_mask)));
}
argtype
rotl32d (argtype v,
unsigned int b)
{
return rotl(v, b);
}
#include <iostream>
#include <bitset>
int
main (int argc, char * argv[])
{
using ostype = std::common_type<unsigned int, argtype>::type;
argtype v {0x1};
int b{8};
if (1 < argc) {
v = std::stoul(argv[1]);
}
if (2 < argc) {
b = std::stoi(argv[2]);
}
std::cout << typeid(argtype).name()
<< " isint "
<< std::is_integral<argtype>::value
<< "\n";
std::cout << std::hex
<< static_cast<ostype>(v) << " rotl " << b << " is "
<< static_cast<ostype>(rotl(v, b)) << "\n";
return 0;
}
@JoshuaGreen

This comment has been minimized.

Copy link

commented May 31, 2014

John Regehr's post is closed, but I still find this topic interesting and useful.
That's some fancy C++11-fu you've got up there, and I'll certainly have to study those techniques in depth at some point. For now, though, I don't think it's all necessary. I think that you can drop the

  using promoted_type = typename std::common_type<int, T>::type;
  using unsigned_promoted_type = typename std::make_unsigned<promoted_type>::type;

lines while replacing

  return ((unsigned_promoted_type{v} << mb)
          | (unsigned_promoted_type{v} >> (-mb & count_mask)));

with

  return ((v + 0U) << mb) | (v >> (-mb & count_mask));

.

@pcordes

This comment has been minimized.

Copy link

commented Jul 18, 2015

I independently came up with the idea of using an AND mask to avoid undefined behaviour when NDEBUG is set (for John Regehr's version). godbolt source: https://goo.gl/3Zt5DK. http://stackoverflow.com/a/31488147/224132 post.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.