unsigned int maxmax( unsigned int a, unsigned int b )
{
unsigned int m;
m = (a+1)/(b+1);
m = (m + 1073741824)/2147483648;
return m*a + (1-m)*b;
}
Same one as before, but a bit faster. Still, not working for (2^32)-1.
Inigo Quilez
A hard problem! Get maximum one of two natural numbers.
unsigned int max(unsigned int a, unsigned int b){ return ((a - b - 1)/0x80000000)*((b - a - 1)/0x80000000)*a + (a/0x80000000)*(b/0x80000000)*(((a - b)/0x80000000)*b + ((b - a)/0x80000000)*a) + ((a + 0x80000000)/0x80000000)*((b + 0x80000000)/0x80000000)*(((a - b)/0x80000000)*b + ((b - a)/0x80000000)*a) + (a/0x80000000)*((b + 0x80000000)/0x80000000)*a + (b/0x80000000)*((a + 0x80000000)/0x80000000)*b;}Ok, nooooooooow I think it's correct. It didn't work for equal numbers, last time. Now, it works for that... and I didn't find any other errors, but also didn't put more than very little effort into it.
If I was giving this question during a interview I would have replied with something like this:
along with the following comment: Documentation is more powerful than code and std::max is more powerful than mine.
I still don't see why answering such a question is important. I don't believe anything is shown by having people trying to solve something that there already exist numerous solutions for. Besides, many people are already nervous and stressed in a interview and thus not performing well in the first place.
namespace math { /** returns the maximum of 2 unsigned integers. * @param a the largest integer * @param b the smallest integer */ unsigned int max(unsigned int a, unsigned int b) { assert(a>b && "a must be larger than b, if this doesn't suit you - use std::max" ); return a; }}along with the following comment: Documentation is more powerful than code and std::max is more powerful than mine.
I still don't see why answering such a question is important. I don't believe anything is shown by having people trying to solve something that there already exist numerous solutions for. Besides, many people are already nervous and stressed in a interview and thus not performing well in the first place.
Thinking is always a good exercise. One should never try and do something before understanding and, to do so, one must practice the mind... stuff like this helps you think in some ways you wouldn't without doing it.
true, but why spend thinking on something that you can access easily and something that "everyone" understands. Writing a list, tree or a hash-map has some value but writing something that exist in the language doesn't serve "game programming". If you want exercise you can do something more productive can write your own engine, a demo or a game.
/imho
edit: slightly off topic - sorry :(
/imho
edit: slightly off topic - sorry :(
I didn't read all of the posts so far, but in about ten minutes I came up with the following:
Therefore:
So h(a,b) = g(a,b) + g(b,a) will give the maximum, unless a = b, in which case the answer is zero. This is half way there.
k is some sort of equality function.
Therefore, one can define:
Which gives the correct answer when a=b.
You may say "But %s aren't allowed!". However: a%b = a-(a/b)*b
So everything is dandy. Now, to give the full thingy:
A mere trifle really (so much so, in fact, that it might be possible to prove it correct). Of course, I think this will screw up horribly when you reach the upper range of the integers. It works if you use natural numbers excluding zero though.
f(a,b) = (a%b)/a = 1 when b>a = 0 when b<=aTherefore:
g(a, b) = f(a,b)*b = b when b>a 0 when b<=aSo h(a,b) = g(a,b) + g(b,a) will give the maximum, unless a = b, in which case the answer is zero. This is half way there.
k(a,b) = 1-f(a,b)-f(b,a) = 1 - 1 - 0 = 0 when b>a = 1 - 0 - 1 = 0 when a>b = 1 - 0 - 0 = 1 when a=bk is some sort of equality function.
Therefore, one can define:
max(a,b) = h(a,b) + a*k(a,b)Which gives the correct answer when a=b.
You may say "But %s aren't allowed!". However: a%b = a-(a/b)*b
So everything is dandy. Now, to give the full thingy:
max(a,b) = h(a,b) + a*k(a,b) = g(a,b) + g(b,a) + a*(1-f(a,b)-f(b,a))= f(a,b)*b + f(b,a)*a + a*(1-f(a,b)-f(b,a))= (a%b)/a*b + (b%a)/b*a + a*(1-(a%b)/a-(b%a)/b)= (a-(a/b)*b)/a*b + (b-(b/a)*a)/b*a + a*(1-(a-(a/b)*b)-(b-(b/a)*a))A mere trifle really (so much so, in fact, that it might be possible to prove it correct). Of course, I think this will screw up horribly when you reach the upper range of the integers. It works if you use natural numbers excluding zero though.
Heres my solution
It should work for any input and any number of bits.
template<typename T>T _UMAX(T a,T b){#define _UMAX_F(x) (((x)*(x))/(((((x)*(x))-1)/2)*2+1))#define _UMAX_G(a,b,c) ((a)*(c))+(b)*(1-(c)) return _UMAX_G(a,b,_UMAX_F(a/(1-_UMAX_F(b)+b)));}#define umax(a,b,type) (_UMAX<unsigned type>((a),(b)))It should work for any input and any number of bits.
I'm suprised at the number of proposed "solutions" that doesn't work!
How about testing your code BEFORE posting it!
A testing program was presented on page 5 for those who are too lazy to create one themself.
How about testing your code BEFORE posting it!
A testing program was presented on page 5 for those who are too lazy to create one themself.
how about this:
unsigned int MaxValue(unsigned int a1, unsigned int a2)
{
return (bool)(a2/(a1+1))*a2 + (bool)(a1/(a2+1))*a1 + (1-(bool)(a1-a2))*a1;
}
unsigned int MaxValue(unsigned int a1, unsigned int a2)
{
return (bool)(a2/(a1+1))*a2 + (bool)(a1/(a2+1))*a1 + (1-(bool)(a1-a2))*a1;
}
Quote:Original post by Anonymous Poster
I'm suprised at the number of proposed "solutions" that doesn't work!
How about testing your code BEFORE posting it!
A testing program was presented on page 5 for those who are too lazy to create one themself.
Mine is correct for natural numbers, but not for any finite subset that overflows.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
