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?

8
  • 6
    What's the "endianness of an integer"? What's the endianness of 15?
    – Kerrek SB
    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. 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? Apr 29, 2016 at 11:22
  • 2
    @BenjaminLindley: Of course. I just find the question vastly underspecified.
    – Kerrek SB
    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. May 11, 2016 at 6:22

3 Answers 3

59

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.

4
  • 7
    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). May 16, 2020 at 23:13
  • 2
    Wasn't me, but thanks for pointing it out - it's nice to have an example that isn't just sum.
    – ecatmur
    May 17, 2020 at 20:42
  • Yeah I definitely appreciated it :) May 19, 2020 at 16:20
  • 2
    Came here because of the cppreference fold docs, and definitely appreciated it too! Dec 18, 2020 at 16:01
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.

4
  • 1
    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.
    – Arne Vogel
    Feb 5, 2018 at 14:44
  • @ArneVogel this is true, I just assumed that the bitmasks will be compile time constants as the function that generates them is a constexpr. Feb 23, 2018 at 12:48
  • 1
    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 Feb 6, 2022 at 2:04
  • 1
    @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 Feb 6, 2022 at 12:27
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

1
  • Not the first nor last instance of the c++ standard taking inspiration from SO. May 14, 2022 at 5:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.