Is there any special C++ function to get XOR of all element of array?

Viewed 287

I have an array like this [1, 0, 1, 1, 0, 0, ...].

How can i get result of this expression: 1 XOR 0 XOR 1 XOR 1 XOR... without loop?

3 Answers

In C++14:

std::accumulate(arr.begin(),
                arr.end(),
                0,
                std::bit_xor<void>())

You could create a function template that takes an array and forwards to a helper function using make_index_sequence - which then uses a fold expression to "unpack" the array.

This does not require any loop since the expression will be created at compile time.

#include <utility>

namespace detail {
template<class T, std::size_t... I>
auto Xor_helper(const T& arr, std::index_sequence<I...>) {
    // make a fold expression of the whole array:
    return (... ^ arr[I]);      // arr[0] ^ arr[1] ^ ...
}
} // namespace detail

template<class T, size_t N>
auto Xor(const T(&arr)[N]) {
     return detail::Xor_helper(arr, std::make_index_sequence<N>{});
}

And you could call it with your array like so:

int main() {
    int arr[] = {0xf, 0x1, 0x3};

    std::cout << std::hex << Xor(arr) << '\n';
}

Output:

d

You can see what becomes of these templates @ cppinsights. Just press the ▶ button and you'll see the above Xor(arr) become return (arr[0UL] ^ arr[1UL]) ^ arr[2UL];


The fold expression above require at least C++17. A solution that works from C++98 and forward could use recursion instead.

Example:

namespace detail {

template<std::size_t> struct index_tag{}; // one type per index used

template<class T, size_t N, size_t I> // main function template
T Xor_helper(const T(&arr)[N], index_tag<I>) {
    // recurse using `index_tag<I - 1>`:
    return Xor_helper(arr, index_tag<I - 1>()) ^ arr[I];
}

// Recursion stops when `index_tag<0>` is used:
template<class T, size_t N>           // terminating case
T Xor_helper(const T(&arr)[N], index_tag<0>) {
    return arr[0]; // no recursion, just return the value
}
} // namespace detail

template<class T, size_t N>
T Xor(const T(&arr)[N]) {
    // Call the helper using the index_tag for the last index in the array:
    return detail::Xor_helper(arr, detail::index_tag<N - 1>());
}

You can also see how these templates will be instantiated @ cppinsights.

It worked: std::accumulate(arr.begin(), arr.end(), arr[0], std::bit_xor());

Related