• entries
    146
  • comments
    436
  • views
    197622

You've Just Won a Trip to Banland!

Sign in to follow this  
Washu

271 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!
Sign in to follow this  


6 Comments


Recommended Comments

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...

Share this comment


Link to comment
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?

Share this comment


Link to comment
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.

Share this comment


Link to comment
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.

Share this comment


Link to comment
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).

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now