26

How to write a constexpr function to swap endianess of an integer, without relying on compiler extensions and can you give an example on how to do it?

Improve this question
8
  • 6
    What's the "endianness of an integer"? What's the endianness of 15? Commented Apr 29, 2016 at 11:10
  • 3
    @KerrekSB Whatever it is. I didn't ask that question. My question is how to swap big-endian to little-endian and vice versa. Commented Apr 29, 2016 at 11:20
  • 8
    @KerrekSB: In the context of C++(and most programming in general), when one says integer, they are usually referring to an integer object. That is, a region in memory used to store integer data, usually one of the fundamental integer types (char, short, int, long and long long, along with their unsigned variants). Have you really never come across that usage? Commented Apr 29, 2016 at 11:22
  • 2
    @BenjaminLindley: Of course. I just find the question vastly underspecified. Commented Apr 29, 2016 at 13:16
  • 12
    @M.M. Well, I disagree, and think the wording is fine. I understand Kerrek's point, but simply think it was needlessly pedantic and dumb. I can't, off the top of my head, think of a better wording for the question, and wouldn't waste my time trying to come up with one, because everybody who knows what endianness is understands it, even Kerrek. Commented May 11, 2016 at 6:22

3 Answers 3

Reset to default
60

Yes, it's pretty easy; here's a recursive (C++11-compatible) implementation (unsigned integral types only):

#include <climits>
#include <cstdint>
#include <type_traits>

template<class T>
constexpr typename std::enable_if<std::is_unsigned<T>::value, T>::type
bswap(T i, T j = 0u, std::size_t n = 0u) {
  return n == sizeof(T) ? j :
    bswap<T>(i >> CHAR_BIT, (j << CHAR_BIT) | (i & (T)(unsigned char)(-1)), n + 1);
}

Example.

Here I'm using j as the accumulator and n as the loop counter (indexing bytes).

If you have a compiler supporting C++17 fold expressions, it's possible to write something that expands out into exactly what you'd write by hand:

template<class T, std::size_t... N>
constexpr T bswap_impl(T i, std::index_sequence<N...>) {
  return ((((i >> (N * CHAR_BIT)) & (T)(unsigned char)(-1)) <<
           ((sizeof(T) - 1 - N) * CHAR_BIT)) | ...);
}; //                                        ^~~~~ fold expression
template<class T, class U = typename std::make_unsigned<T>::type>
constexpr U bswap(T i) {
  return bswap_impl<U>(i, std::make_index_sequence<sizeof(T)>{});
}

The advantage of this form is that because it doesn't use loops or recursion, you're pretty much guaranteed to get optimal assembly output - on x86-64, clang even manages to work out to use the bswap instruction.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

You might be interested to know this answer is linked to by cppreference's fold expression docs (not sure if you put them there yourself or if someone else did).
Wasn't me, but thanks for pointing it out - it's nice to have an example that isn't just sum.
Yeah I definitely appreciated it :)
Came here because of the cppreference fold docs, and definitely appreciated it too!
4

Inspired by ecatmur I suggest the following solution, that has potentially better performance when bswap is not detected by the compiler (O(log(n)) vs O(N)). Given that N is usually <=8 this is probably irrelevant, still:

using std::numeric_limits;

template <typename T>
typename std::enable_if<std::is_unsigned<T>::value,T>::type
constexpr alternating_bitmask(const size_t step){
  T mask(0);
  for (size_t i=0;i<numeric_limits<T>::digits;i+=2*step){
    mask|=(~T(0)>>(numeric_limits<T>::digits-step))<<i;
  }
  return mask;
}

template <typename T>
typename std::enable_if<std::is_unsigned<T>::value,T>::type
constexpr bswap(T n){
  for (size_t i=numeric_limits<unsigned char>::digits;
              i<numeric_limits<T>::digits;
              i*=2) {
    n = ((n&(~(alternating_bitmask<T>(i))))>>i)|
        ((n&( (alternating_bitmask<T>(i))))<<i);
  }
  return n;
}

As this form is more complex than ecatmur's solution the compiler has a harder job optimizing, but clang still finds out that we mean bswap.

Improve this answer

4 Comments

This solution actually has a time complexity of Θ(N) as well because the inner loop (not counting optimizations) has an amortized complexity of Θ(N / log N) (per iteration of the outer loop). To get actual Θ(log N), the bitmasks would need to be memoized, e.g. precomputed into an array.
@ArneVogel this is true, I just assumed that the bitmasks will be compile time constants as the function that generates them is a constexpr.
This code does not compile (since digits<T> is not defined). Upon replacing digits<T> by std::numeric_limits<T>::digits from limits.h, the code compiles starting at C++14 and DOES NOT swap the bytes. godbolt.org/z/YfhETebM3
@AdomasBaliuka I fixed the compilation error and tested it. It works, but be careful to use unsigned char , char alone is 7 bit. clang++ even recognizes this as bswap, have a look at the assembler: gcc.godbolt.org/z/5Mozedzvo
1

Finally, C++23 allows to do this easily with the new function std::byteswap from the Standard Library: https://en.cppreference.com/w/cpp/numeric/byteswap

Improve this answer

1 Comment

Not the first nor last instance of the c++ standard taking inspiration from SO.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.