Given eight integers, what is the fastest way to check if they are all the same or not? Maybe, some clever bit manipulation?
Following appeals to me.
bool EightNumbersEqual(a,b,c,d,e,f,g,h)
{
return (a|b|c|d|e|f|g|h)==a ? true : false;
}
You can expand it to unknown amount of checked numbers, and I believe it will work for any numerical type since of the bits->number determinism.
return (a|b|c|d|e|f|g|h)==a ? true : false;
Nope. That will lead to all kinds of fun bugs. Any value can be any value as long as it sets no more bits than were set by a.
If a == 0x01, then values can be either 1 or 0.
If a == 0xff, then any value is allowed in all the other values.
(Extend it to whatever length or size is needed, maybe they're 8-bit chars, maybe they're 512 bit AVX registers, maybe they're some custom bignum class.)
EDIT: For the 64bit trick, the array better be alignas(uint64_t), and I'm not 100% sure if that reinterpret_cast is actually legit in C++ (it would be undefined behavior in C at least due to strict aliasing requirements). It might be safer to work around it using unions, but the generated code seems fine.
Assuming the array is originally a char*, there is no violation of the strict aliasing rule, as char* is the only datatype that can alias to anything. Though you are right we would have to concern about the compiler not blowing up the performance part; it may be faster/safer to just keep it always as uint64_t and use "& 0xFF" to get the table index due to language shenanigans.
Wow, thanks for so many high-quality answers!!
I'll go with Álvaro's (brilliant) trick for now!
(I needed a fast function, because it's executed for each cell out of 33^3 (in each voxel chunk). If voxels at the cell's corners are different, then a material transition is taking place and the cell must contain a surface vertex.)
bool EightNumbersEqual(a,b,c,d,e,f,g,h)
{
return (a^b|a^c|a^d|a^e|a^f|a^g|a^h)==0 ? true : false;
}
Guys, I strongly believe this one works, but my question is... would this be any faster/slower than a single integer number multiplication?
I needed a fast function, because it's executed for each cell out of 33^3 (in each voxel chunk). If voxels at the cell's corners are different, then a material transition is taking place and the cell must contain a surface vertex.
Profiler or it didn't happen.
My favourite quick-prototyping tool for deciding whether or not a code rewrite has the intended effect on what the compiler produces:
Frob's loop code: https://godbolt.org/g/HEFMYz
Frob's manually unrolled code: https://godbolt.org/g/MZrQRH
JonnyCode's obfuscated XOR trickery: https://godbolt.org/g/3UAbN5
I'll admit that what JonnyCode's written is what you want, if you want a constant-time algorithm (which is something you want in some algorithms, to prevent a certain class of cryptographic attack)... but as you can see, the transformation from "do what I mean" code to the less-readable "do what I say" code does not have a noticeable effect on total instruction count or (admittedly eyeballed) clock cycles. In the worst case scenarios, there's just as many register/ALU round trips, and there's just as many fetches made.
But as Khatharr says, as will every other developer worth his salt: you don't know where the actual time is being spent in your algorithms until you profile it. Even when you guess correctly, it is only a guess. Analysis of evidence is more valuable than analysis of theory.
