xor the elements of two vectors

[bitrex]

I'm looking for the efficient/modern C++ way to bitwise xor element-wise
the objects contained in two std::vectors, and stuff the resultant
values into new vector of the same length as the original two.

I think this can be done with a lambda function? and a mapping function
on the vectors but don't immediately know the procedure I would use.

Thank you

[Alf P. Steinbach]

Lambdas can be used for anything but why not just use a simple loop.

KISS, Keep It Simple, Stupid.

Off the cuff:

using Size = ptrdiff_t;

template< class Item >
auto xor_of( const vector<Item>& a, const vector<Item>& b )
-> vector<Item>
{
vector<Item>& short_vec = (a.size() < b.size()? a : b);
vector<Item>& long_vec = (a.size() < b.size()? b : a);

vector<Item> result( short.size() );
for( Size i = 0, n = short.size(); i < n; ++i ) {
result[i] = short_vec[i] ^ long_vec[i];
}
for( Size i = short_vec.size(), n = long_vec.size(); i < n; ++i ) {
result[i] = long_vec[i];
}
return result;
}


Cheers!,

- Alf

[Alf P. Steinbach]

Oh, the result should be of the longest size, not shortest.

Anyway.


Cheers!,

- Alf

[bitrex]

Thank you, I'm curious why is ptrdiff_t used in this context instead of
size_t?

[Chris M. Thomasson]

For what its worth, and is probably off topic... One can get some
interesting xors using the xy plane. Now, afaict, this can be extended
to fill the 3d space. Here is a very simple, crude real time example:

https://www.shadertoy.com/view/4lffzM

It shows the patterns on the xy xor'ing playground, so to speak...

[Alf P. Steinbach]

A general rule-of-thumb: to avoid unsigned thumbs /for numbers/, but do
use them for bit-level stuff.

Mainly the rationale of that rule is that the promotion rules in modern
C and C++, which in C++ guarantee that e.g.

std::string( "Hello" ).length() < -2

... makes code that uses unsigned types used for numbers very attractive
to bugs.

Sort of like making a sugar trail into the house and leaving the door open.


Cheers!,

- Alf

[Alf P. Steinbach]

On 06.06.2019 09:06, Alf P. Steinbach wrote:
>
> to avoid unsigned thumbs /for numbers/,

Well I meant to write "types".

My text generation subsystem works in mysterious ways.


Cheers!,

- Alf

[David Brown]

On 06/06/2019 09:42, Alf P. Steinbach wrote:
> On 06.06.2019 09:06, Alf P. Steinbach wrote:
>>
>> to avoid unsigned thumbs /for numbers/,
>
> Well I meant to write "types".
>

I thought it made perfect sense, given that it was a rule of thumbs!

[Rick C. Hodgin]

On Wednesday, June 5, 2019 at 11:17:30 PM UTC-4, Chris M. Thomasson wrote:
> https://www.shadertoy.com/view/4lffzM

It looks more like a video game screen if you change this:

int xy_xor = (x + iFrame/2) ^ (y*2);

You can just see the Farmville plots of land down there. :-)

--
Rick C. Hodgin

[Jorgen Grahn]

The function would be xor(a, b) -- is there a std::xor already?

The mapping would be one of the variants of std::transform. Untested:

std::transform(begin(vector1), end(vector1),
begin(vector2),
begin(dest),
xor);

You need to make room in 'dest' first, and check that vector2 is at
least as large as vector1. Check the details at e.g. cppreference.com.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[leigh.v....@googlemail.com]

If you are a proponent KISS then why aren't *you* keeping it simple by using auto return type when you don't have to, stupid?

/Leigh

[Alf P. Steinbach]

Trailing return type syntax is generally simpler than the old syntax.

For example, instead of

MyLongClassName::Blah MyLongClassName::foo( Blah x )

... you can write just

auto MyLongClassName::foo( Blah x ) -> Blah

Same rule for return type spec and argument spec = simpler, and shorter.

It's also simpler in a number of other cases, e.g. consider a function
returning a reference to an array.


Cheers!,

- Alf

[Öö Tiib]

Yes, it was what I liked in Fortran, Pascal and Ada and disliked in C.
Also several popular modern C-like languages (like Rust, Swift,
Kotlin) have corrected it back to that logical way. Starting from
scratch I would consider it. However most things are done using
tons of already existing code and libraries and also majority of
good C++ programmers are aging and conservative. One does
not want to have inconsistent style all over the code base.
So it is perhaps tricky to switch for both practical and political
reasons.

[Mr Flibble]

However in *most* cases (including the case you posted) the version with
auto is longer/more complex than the equivalent version without auto so I
am sorry Alf but your argument simply doesn't wash. You even use it for
main() but I think you do that just to piss people off. One should only
use auto return when there is a clear need for it. STOP CAUSING PANIC.

/Flibble

--
"Talking snakes with legs changed into snakes." - Rick C. Hodgin

“You won’t burn in hell. But be nice anyway.” – Ricky Gervais

“I see Atheists are fighting and killing each other again, over who
doesn’t believe in any God the most. Oh, no..wait.. that never happens.” –
Ricky Gervais

"Suppose it's all true, and you walk up to the pearly gates, and are
confronted by God," Bryne asked on his show The Meaning of Life. "What
will Stephen Fry say to him, her, or it?"
"I'd say, bone cancer in children? What's that about?" Fry replied.
"How dare you? How dare you create a world to which there is such misery
that is not our fault. It's not right, it's utterly, utterly evil."
"Why should I respect a capricious, mean-minded, stupid God who creates a
world that is so full of injustice and pain. That's what I would say."

[Mr Flibble]

And Satan invented fossils, yes?

[Rick C. Hodgin]

On Thursday, June 6, 2019 at 1:40:51 PM UTC-4, Mr Flibble wrote:
> And Satan invented fossils, yes?

Nope. But, he does convince people to be hateful to those who
bear them no harm whatsoever. He causes amazing people made in
the very image and likeness of God to set all that aside, to set
their intelligence aside, and switchover to the mental equivalence
of a five-year old's running around in circles away from their
mommy screaming "blah blah blah blah blah" mode ... intellectually.

You have demonstrated quite the personage, Leigh. Vulgar, obscene,
profane, mean, belittling, bullying, arrogant, prideful, and you
hide behind masks (posting as "Mr. Flibble" rather than Leigh).
Are you ashamed of your own identity? You want to be someone else?

There is peace in knowing Jesus Christ. You realize who you are,
why you need to repent and ask forgiveness, and then He cleanses
you of your unrighteousness before God. It fills you with calm and
joy on the inside like none other.

--
Rick C. Hodgin

[Mr Flibble]

Nonsense.
A) Your bible is false.
B) Your god the existence of which is predicated on your bible being true
is, given (A), also false.

[Rick C. Hodgin]

On Thursday, June 6, 2019 at 2:45:21 PM UTC-4, Mr Flibble wrote:
> Nonsense.
> A) Your bible is false.
> B) Your god the existence of which is predicated on your bible being true
> is, given (A), also false.

Alright. I want to get in on this too, Leigh. It looks like fun.

2 + 2 = 5

Okay ... just so I don't waste my time ... how many times will
I have to post this over and over before it becomes true?

Wait! Wait. No. Perhaps that's the wrong question.

Okay. In estimating your attempts at making your false statement
come true to date, I know it's at least a few hundred. Maybe a
few thousand?? So, I guess the better question would be: How
long until YOUR false statement becomes true?

--
Rick C. Hodgin

[Richard]

[Please do not mail me a copy of your followup]

Jorgen Grahn <grahn...@snipabacken.se> spake the secret code
<slrnqfi4fe.c...@frailea.sa.invalid> thusly:

>On Thu, 2019-06-06, bitrex wrote:
>> I'm looking for the efficient/modern C++ way to bitwise xor element-wise
>> the objects contained in two std::vectors, and stuff the resultant
>> values into new vector of the same length as the original two.
>>
>> I think this can be done with a lambda function? and a mapping function
>> on the vectors but don't immediately know the procedure I would use.
>
>The function would be xor(a, b) -- is there a std::xor already?
>
>The mapping would be one of the variants of std::transform. Untested:
>
> std::transform(begin(vector1), end(vector1),
> begin(vector2),
> begin(dest),
> xor);

This, yes, this is just what I was going to post :-)

>You need to make room in 'dest' first, [...]

Or you can use a back_inserter from <iterator>:

std::transform(begin(vector1), end(vector1),
begin(vector2),
back_inserter(dest),
xor);

--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[Chris M. Thomasson]

On 6/6/2019 10:40 AM, Mr Flibble wrote:
> On 06/06/2019 13:04, Rick C. Hodgin wrote:
>> On Wednesday, June 5, 2019 at 11:17:30 PM UTC-4, Chris M. Thomasson
>> wrote:
>>> https://www.shadertoy.com/view/4lffzM
>>
>> It looks more like a video game screen if you change this:
>>
>>      int xy_xor = (x + iFrame/2) ^ (y*2);
>>
>> You can just see the Farmville plots of land down there. :-)
>
> And Satan invented fossils, yes?

This is about having fun with XOR... No?

[james...@alumni.caltech.edu]

On Thursday, June 6, 2019 at 9:15:36 AM UTC-4, Jorgen Grahn wrote:
...

> The function would be xor(a, b) -- is there a std::xor already?

There's std::bit_xor.
xor is a token in it's own right (5.5p2), so it can't be used as an identifier.

[Mr Flibble]

And Satan invented fossils, yes?

[Chris M. Thomasson]

On 6/6/2019 10:13 PM, Mr Flibble wrote:
> On 06/06/2019 20:00, Rick C. Hodgin wrote:

[...]

> And Satan invented fossils, yes?

Did it invent XOR?

[Cholo Lennon]

But Alf, you use trailing return type syntax for function main :-O

Regards

--
Cholo Lennon
Bs.As.
ARG

[Öö Tiib]

But *if* to use trailing return style for non-void functions then
most logically all code-base should use it and only it
(including definition of main).

Unfortunately C++ hasn't added trailing type syntax to
"variables" so such style would still feel half-baked.

Most logical declaration order of data element is
something like that:
1) indicate first the kind of citizen. IOW if what we declare is
constant or variable (if the language has both). If language
does not have both then indicate if it is code or data (if the
language makes difference between the two). In C++ it is
question if it is "variable" or "reference" ("alias" would be
more precise term about "reference") and if its value is
mutable or immutable. Notice slight nonsensicality of
English: how can it "vary" when being "immutable" or even
"compile-time immutable"?
2) Then comes name as most important property of citizen.
3) Then we should give it (initial) value. That is mandatory
for constants whose declaration does coincide with
start of life-time but can be optional for variables.
4) Finally there may be need to indicate its type if
language enforces type of an data element to be
immutable during its life-time. Even then it is optional
for variables that have initial value.

It would look something like

constexpr answer = 42 : uint8_t;

However that all is too trivial to rearrange in our brains
so I don't think we should somehow extend C++ for
getting that minor clarity benefit. All the human languages
are far less logical than C++ (that majority of programmers
curse with passion), but we use those with ease.

[Mr Flibble]

Why only for non-void functions? If your primary concern is consistency
then be fucking consistent.

[Ian Collins]

If you want simple, use simple. Your function definition doesn't even
need the trailing return type and could just be written

auto xor_of( const vector<Item>& a, const vector<Item>& b )

{

I tend to only use auto return deduction when the compiler can do the
work for me!

--
Ian.

[Mr Flibble]

I class that as obfuscation: I no longer know what the function return
type is without recourse to looking at the function body.

/Flibble

--
"Snakes didn't evolve, instead talking snakes with legs changed into

[Chris M. Thomasson]

Ahhhh! I see this. It is more elliptical. And it does seem to posses a
strange 3d quality that allows one to say, "look at the farms _down_
there". A game comes to mind...

Thanks Rick! :^D

Thanks.

[David Brown]

On 08/06/2019 00:52, Mr Flibble wrote:
> On 07/06/2019 23:49, Ian Collins wrote:
>> On 07/06/2019 04:42, Alf P. Steinbach wrote:

<snip>

>>> Trailing return type syntax is generally simpler than the old syntax.
>>
>> If you want simple, use simple.  Your function definition doesn't even
>> need the trailing return type and could just be written
>>
>> auto xor_of( const vector<Item>& a, const vector<Item>& b )
>> {
>>
>> I tend to only use auto return deduction when the compiler can do the
>> work for me!
>
> I class that as obfuscation: I no longer know what the function return
> type is without recourse to looking at the function body.
>

If the return type is clear from the name of the function, you don't
need to look in the body. If it is /not/ clear, then maybe the function
should have a better name (say, "vector_xor"). (This is, of course,
going to be highly subjective and dependent on the context of the rest
of the code.)

The point is, you avoid obfuscation by making things clear - but that
does not necessarily mean rigid consistency in the way you write things.
I personally think the advantage of having three different ways of
specifying return types is that you can pick the one that makes most
sense, is clearest, and least likely to have errors - using the method
that is best in any given case.

[Juha Nieminen]

bitrex <us...@example.net> wrote:
> I'm looking for the efficient/modern C++ way to bitwise xor element-wise
> the objects contained in two std::vectors, and stuff the resultant
> values into new vector of the same length as the original two.
>
> I think this can be done with a lambda function? and a mapping function
> on the vectors but don't immediately know the procedure I would use.

I find this question extraordinarily confusing. I find it confusing
because, I suppose, I don't really understand what you are asking.

Iterating through a couple of vectors, xorring the elements and
assigning the result into a third vector is a 2-liner. And it's not
like it's some really obscure highly-technical hacker-trick that you
need deep understanding of C++ or programming to do. It's an extremely
simple, even trivial, thing to do, even for a complete beginner. Just
write a single for-loop with an assignment as its body. Two lines of
very simple code.

So, because this is so simple, I'm suspecting that's *not* what you
are really asking. You seem to be asking something else. But what,
exactly?

Maybe you are asking if there's an even faster way of doing that
other than just iterating through the vectors? You could most certainly
improve on the speed of that task by helping the compiler to vectorize
the code (ie. help it use SIMD instructions to perform the xorring on
4 or even 8 elements at a time), and/or by using multithreading.
Especially the former *is* a bit of a more profound technique that
requires a bit of undrestanding of what the compiler is doing, and what
you can do to help it vectorize the code.

However, you then start talking about lambda functions, completely
out of the blue. This confuses me even more. Maybe you aren't actually
talking about how to make the code faster. Maybe when you say
"efficient" you are not talking about execution speed, but something
else? Why would you be talking about lambda functions if all you cared
is executiong speed? What do lambda functions have anything to do with
this? I suspect that you are asking for something else.

I just don't understand what.

[Mr Flibble]

On 09/06/2019 11:17, Juha Nieminen wrote:
> bitrex <us...@example.net> wrote:
>> I'm looking for the efficient/modern C++ way to bitwise xor element-wise
>> the objects contained in two std::vectors, and stuff the resultant
>> values into new vector of the same length as the original two.
>>
>> I think this can be done with a lambda function? and a mapping function
>> on the vectors but don't immediately know the procedure I would use.
>
> I find this question extraordinarily confusing. I find it confusing
> because, I suppose, I don't really understand what you are asking.
>
> Iterating through a couple of vectors, xorring the elements and
> assigning the result into a third vector is a 2-liner. And it's not
> like it's some really obscure highly-technical hacker-trick that you
> need deep understanding of C++ or programming to do. It's an extremely
> simple, even trivial, thing to do, even for a complete beginner. Just
> write a single for-loop with an assignment as its body. Two lines of
> very simple code.

As Jorgen suggested up-thread the idiomatic way to do this is using
std::transform rather than with explicit for-loops and it does indeed make
it a one liner in which use of a lambda would be appropriate if std::xor
didn't exist.

[Juha Nieminen]

Mr Flibble <flibbleREM...@i42.co.uk> wrote:
> As Jorgen suggested up-thread the idiomatic way to do this is using
> std::transform rather than with explicit for-loops and it does indeed make
> it a one liner in which use of a lambda would be appropriate if std::xor
> didn't exist.

I see absolutely no reason to not use a for-loop. It's not harder to
understand.

Using a for-loop may also allow for more speed optimizations.
std::transform might or might not perform speed optimizations itself,
but it's of course not guaranteed.

[Öö Tiib]

On Friday, 7 June 2019 16:54:17 UTC+3, Mr Flibble wrote:
> On 07/06/2019 09:52, Öö Tiib wrote:
> > But *if* to use trailing return style for non-void functions then
> > most logically all code-base should use it and only it
> > (including definition of main).
>
> Why only for non-void functions? If your primary concern is consistency
> then be fucking consistent.

Because "function" that returns nothing is different kind of
citizen ("procedure", "subroutine") than "function" in lot
of programming languages for reason.
Therefore "constexpr auto" - pure function, "auto" - impure
function or "void" - procedure at start of declaration would
add that clarity.

[Öö Tiib]

So usage of std::transform might result with extra speed optimizations
and/or usage of for loop might result with extra speed optimizations
but neither is guaranteed.

Therefore if we think that efficiency may be different then we have
to profile both. We have to profile in context of actual usage,
compiled with actual production compiler/flags and ran on actual
target hardware. Doing it in some toy benchmark or newsgroup
post shows nothing.

[Juha Nieminen]

Öö Tiib <oot...@hot.ee> wrote:
>> Using a for-loop may also allow for more speed optimizations.
>> std::transform might or might not perform speed optimizations itself,
>> but it's of course not guaranteed.
>
> So usage of std::transform might result with extra speed optimizations
> and/or usage of for loop might result with extra speed optimizations
> but neither is guaranteed.

What I meant is that the for-loop may allow for "manual" speed
optimization by the programmer (such as using #pragma omp).

[Chris Vine]

I agree with what you say except that since std::transform is a
template function the compiler is going to have pretty much the same
optimization opportunities as with a well-written hand-written loop.

Using the C++ algorithms where relevant such as std::transform (map),
std::accumulate (fold/reduce), std::adjacent_difference (differentiate),
std::partial_sum (integrate), std::rotate, std::stable_partition and
std::partial_sort makes code significantly easier to understand, and it
generally annoys me when people try to do exactly the same by hand (and
usually less well and obscurely). People often seem to do this through
ignorance.

[james...@alumni.caltech.edu]

On Thursday, June 6, 2019 at 9:15:36 AM UTC-4, Jorgen Grahn wrote:

> On Thu, 2019-06-06, bitrex wrote:
> > I'm looking for the efficient/modern C++ way to bitwise xor element-wise
> > the objects contained in two std::vectors, and stuff the resultant
> > values into new vector of the same length as the original two.
> >
> > I think this can be done with a lambda function? and a mapping function
> > on the vectors but don't immediately know the procedure I would use.
>

> The function would be xor(a, b) -- is there a std::xor already?

As far as I can tell, no. If such a thing could exist (see below) I'd expect it to be described in section 23.14.9, and it's not there. However, std::bit_xor does exist, and std::bit_xor(a,b) is defined as a^b.

There's a good reason why std::xor() can't exist: xor is defined as an alternative token (5.5p2), and therefore cannot be used as an identifier.

> The mapping would be one of the variants of std::transform. Untested:
>
> std::transform(begin(vector1), end(vector1),
> begin(vector2),
> begin(dest),
> xor);

Because xor is an alternative token, that results in the following messages when I try to compile it:

error: expected primary-expression before ‘xor’ token
xor);
^~~
error: expected primary-expression before ‘)’ token
xor);
^

[Öö Tiib]

See execution policies added to algorithm library since C++17 and
notice that you can pass those to std::transform:
https://en.cppreference.com/w/cpp/algorithm/transform

[Öö Tiib]

I have same views but for Juha it is as readable or even better readable.
There that then goes to territory of "matter of taste". About taste it is
possible to fight but not to argue. So all I can say is that if compiler
and/or library uses some special optimization opportunities/magics on
one or other case is up to implementation and sometimes expensive to
measure.

[Chris M. Thomasson]

On 6/5/2019 5:02 PM, bitrex wrote:
> I'm looking for the efficient/modern C++ way to bitwise xor element-wise
> the objects contained in two std::vectors, and stuff the resultant
> values into new vector of the same length as the original two.
>
> I think this can be done with a lambda function? and a mapping function
> on the vectors but don't immediately know the procedure I would use.
>

> Thank you


Take some vectors, any vectors... convert them to pixels with integers
in the 2d pixel plane. On or off plane, Xor each component together...
convert them back, PLOT. Can do! Or, is this way off topic?

[Chris M. Thomasson]

Humm... I need to try this for fun. I just want to see the darn visual
result! :^)

[Chris M. Thomasson]

Start with an even number of, say, complex numbers, in a shape...
Project them all the way down to the integer pixel realm, so final 2d
vectors in a sense... Xor their components together. Plot the origin
pixel and the xored pixel, and perhaps move them back to the complex
plane and perform some other fun stuff...

[Juha Nieminen]

Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
> Using the C++ algorithms where relevant such as std::transform (map),
> std::accumulate (fold/reduce), std::adjacent_difference (differentiate),
> std::partial_sum (integrate), std::rotate, std::stable_partition and
> std::partial_sort makes code significantly easier to understand, and it
> generally annoys me when people try to do exactly the same by hand (and
> usually less well and obscurely). People often seem to do this through
> ignorance.

In the case of xorring the elements of two vectors into a third vector
it's a matter of opinion which way is clearer and easier to read and
understand.

One could argue that most programmers are more accustomed to seeing and
understanding explicit for-loops, especially those that are a two-liner
(like in this case), than a more unusual call to a standard library
function (that, at a very quick glance, doesn't even look like a loop
at all, until you start reading the details). Of course this is more a
matter of what the programmer is accustomed to.

The original poster might have not had execution speed in mind when he
asked the question (even though he used the word "efficient", but I get
the feeling he used that word to mean something else than execution
speed; maybe something like "efficient in terms of amount of source
code", or perhaps "efficient in terms of readability", or something
along those lines?) However, a "manual" implementation might allow for
some low-level optimizations that are in no way guaranteed to be done by
std::transform.

Assume that this particular task needs to be done as efficiently as the
hardware just can do it, squeezing every possible clock cycle away from it,
achieving as much throughput as is available (while still keeping it fully
standard C++).

One method that even many experienced C++ programmers aren't aware of,
and haven't studied, is SIMD vectorization. Modern compilers can be
surprisingly good at generating vectorized SSE code (or whatever the
equivalent is in the target architecture, like ARM64), but in many cases
you need to "help" the compiler a bit.

For example, if you are doing a simple operation like this to a very
large amount of ints, for instance, it can become much faster if you
do it to 8 ints in an inner loop at once. In other words, rather than
just write the simple singular loop, you write an inner loop that
simply does the operation to 8 elements. There's a very high chance
that the compiler will optimize that inner loop into a single SSE
instruction that does the operation to all 8 elements at once.
If the compiler was not already doing this with the simple loop,
the result may speed up by well over a factor of 2.

[Stefan Große Pawig]

bitrex <us...@example.net> writes:
> I'm looking for the efficient/modern C++ way to bitwise xor
> element-wise the objects contained in two std::vectors, and stuff the
> resultant values into new vector of the same length as the original
> two.

If the use of std::vector is not set in stone, you could also check
std::valarray. It provides this kind of functionality out of the box.

--- 8< ---
#include <valarray>
#include <iostream>
#include <iomanip>

int main() {
const std::valarray<int> x{ 0x00, 0x33, 0x55, 0xff };
const std::valarray<int> y{ 0x11, 0x11, 0x11, 0x11 };

const std::valarray<int> z = x ^ y;

for (auto d : z)
std::cout << std::hex << d << "\n";
}
--- >8 ---

-Stefan