• entries
146
436
• views
198763

You've Just Won a Trip to Banland!

295 views

template struct a {    static unsigned int b(unsigned int x, unsigned int y) {        return ((x<<(N-1)) & (~(((y>>(N-1)) & 1) - 1))) + a1>::b(x, y);    }};template<> struct a<1> {    static unsigned int b(unsigned int x, unsigned int y) {        return (x & (~(((y) & 1) - 1)));    }};

Any guesses as to what this does, and how it works? To those of you whome I've already told...you cannot speak less yee die!

I feel an urge to refactor that into all my projects, it's so cool.

Without looking at it in much detail, it looks like it does something like returns the next highest power of 2 of a number. Or something weird with bit shinnanigans anyway...

Quote:
 Original post by Washu Any guesses as to what this does, and how it works? To those of you whome I've already told...you cannot speak less yee die!

Abuses the compiler?

Don't scroll down if want to solve it yourself

It multiplies an unsigned number x with
the first n bits of another unsigned number y.
It works by breaking down y into it's power-of-2
terms and multiplying them individually with x.
So for 5 and 7 it works by using
5*7 == 5*(1+2+4) == 5*1+5*2+5*4. Of course it
doesn't actually multiply anywhere, but instead
it uses the fact that a*2^n == a << n

Note: ^ is the power operator while << is the shift left operator and == is the equality operator.



Now, how and why do you come up with these things?

Washu - "Any guesses as to what this does, and how it works? To those of you whome I've already told...you cannot speak less yee die!"

It is obviously meant to confuse the reader of the code. It does so by using templates and very large numbers of parenthesis.
I can also make an attempt at guessing why it does that, which i believe is increasing the job security of the code writer, by ensuring that no one else can mantain the code.

I used MSDN as a reference to find out what ~ does.
// spoiler dont scroll if you want to do it yourself

// a<N>::b(x, y) is equivelent to (in psuedo code)
unsigned int result = 0;
for (unsigned int i = N; i > 0; --i)
{
if (y > 2 ^ (N - 1))
{
result += x * 2 ^ (N - 1);
}
}

// or expressed mathimatically
x * sum(2 ^ i, i = 0..min(N - 1, floor(log2(y))))

// My Reasoning....

// I started with the base case a<1>....
(x & (~(((y) & 1) - 1))) = (x & (~((y & 1) - 1)))
= (x & (~((y ? 1 : 0) - 1)))
= (x & (~(y ? 0 : -1)))
= (x & (y ? std::numeric_limits<unsigned int>::max : 0))
= (y ? x : 0)

// (i had to look up what ~ was on msdn, silly ones complement)
// Then I moved on to the more general case a<N>....
((x<<(N-1)) & (~(((y>>(N-1)) & 1) - 1))) + a<N-1>::b(x, y)
= (y >> (N - 1) ? x << (N - 1) : 0) + a<N-1>::b(x, y)
= (y >> (N - 1) ? x * 2 ^ (N - 1) : 0) + a<N-1>::b(x, y)
= (y > 2 ^ (N - 1) ? x * 2 ^ (N - 1) : 0) + a<N-1>::b(x, y)

// EDIT: Simplified final result, sum of GP silly me
x * (2 ^ max(N - 1, floor(log2(y))) - 1)

// EDIT: Gaaarrrrr this is why C++ is so bad, i did the (y >> (N-1)) & 1 with a
// logical and instead of a bitwise now i see why CTar's right



If thats wrong then my bets on undefined bahviour.

Reminds me of a method i came up with to add one to a signed integer without using + or - ... or & and | to that matter. It's not as creative but it's in the same vain.

int add_one(int a)
{
return (~0) * ~a;
}

int sub_one(int a)
{
return ~((~0) * a);
}


It works because the difference between bitwise-not and multiplying by -1 is 1. Definitely the wrong way to add one but it does work. Ironically in the scripting language that i am forced to do work in, using (c=-~c) or (c=~-c) is faster then using (++c) or (--c) (not to mention the environment has very little memory to work with, and using this hack uses less memory).

Create an account

Register a new account