Jump to content
  • Advertisement
Sign in to follow this  
CTar

Custom unsigned int (64 bit) divide

This topic is 4852 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I needed an 64 bit unsigned int for some encryption and timing code, I chose (just for fun) to write an 64 bit unsigned int class myself. The problem is that I have figured out how to code the +, - and * operators, but I dont know how to perform a divide, I store the 64 bit unsigned int as two unsigned ints with the size of 32 bit(on most compilers "unsigned int"). So does anyone know how to do such a divide.

Share this post


Link to post
Share on other sites
Advertisement
I'd advise to use explicit 64 bit variable definition instead of something like long long. I feel a bit strongly about explicit typing of variable types ever since we moved our mmog server from linux 32 bit to linux 64 bit. Ah the hours of fun ^_^.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I'm czar here..... (and of #Czar, and hopefully will be in #Australia and #Gamedev)....

Easy way is to just use multiple additions. (ie. if it takes 200 additions to get the numerator to be larger then the demoninator, then the answer is 200).

A harder way is to multiply the number your adding by two, then adding some code to move the number back. This gets you the answer faster, but is more complex.

Czar.

Share this post


Link to post
Share on other sites
Quote:
Original post by Catafriggm
No, but I would highly suggest you use long long or some compiler-dependant 64-bit type, instead.


Well I want it to work on all compiler supporting standard C++, in the actual code I'll have a typedef named UInt32 which is set to a compiler dependent type if it is available (testing with preprocessor), if no 64-bit type is available I'll use my custom one.

I dont do this to get performance, but because I need something to write.

Share this post


Link to post
Share on other sites
Hmmm I vaguely remember the algorithm but I can't seem to get the details right..

Anyway, the short answer is it's just like long division from school. Except it's long division with binary numbers, which is actually easier.

Share this post


Link to post
Share on other sites
Okay I think I remember it:

Say we are solving a / b


int answer = 0;
int a_shifted = 0;

for (int i=0; i < 64; i++)
{
a_shifted << 1;
a_shifted += (a >> (63 - i)) & 1; // stick the most significant bit of 'a' onto the right side of a_shifted
answer << 1;
if (a_shifted >= b)
{
answer += 1; // remember long division where you write the number up top?
a_shifted -= b; // then you do the little subtraction underneath
}
}


I think that will work. It's untested so there's probably a few off-by-one errors in there.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
typedef unsigned __int64 ulong64;

ulong64 a=23804523582523535235;
ulong64 result = a / 8523523532;

Share this post


Link to post
Share on other sites
Thanks for all the answers.

Pinacolada: Thanks, I will check it out tommorow, but I have to go to bed now(2:40AM here) and need to code a few operators before trying your code.

AP: __int64 is not standard C++, it is MSVC specific(maybe other compilers too). The whole purpose of this class was to create a standard C++ 64 bit unsigned int.

Share this post


Link to post
Share on other sites
Here's the division function from my own u64 class. Only reason I wrote the damn thing was to maintain portability.


void Divide(u64& dividend,const u64 divisor,const bool wantQuotient)
{
u64 remainder(0);
u64 quotient(0);

if (divisor < dividend)
{
unsigned int bits = 64;

do
{
remainder.hi = (remainder.hi << 1) | (remainder.lo >> 31);
remainder.lo = (remainder.lo << 1) | (dividend.hi >> 31);
dividend.hi = (dividend.hi << 1) | (dividend.lo >> 31);
dividend.lo = (dividend.lo << 1);
--bits;
}
while (remainder < divisor);

for (;;)
{
u64 tmp(remainder);
tmp -= divisor;

quotient.hi = (quotient.hi << 1) | (quotient.lo >> 31);
quotient.lo = (quotient.lo << 1);

if (!(tmp.hi & 0x80000000UL))
{
quotient.lo |= 0x1;
remainder = tmp;
}

if (!bits)
break;

--bits;

remainder.hi = (remainder.hi << 1) | (remainder.lo >> 31);
remainder.lo = (remainder.lo << 1) | (dividend.hi >> 31);
dividend.hi = (dividend.hi << 1) | (dividend.lo >> 31);
dividend.lo = (dividend.lo << 1);
}
}
else if (divisor == dividend)
{
quotient = 1;
}
else
{
remainder = dividend;
}

if (wantQuotient)
dividend = quotient;
else
dividend = remainder;
}

// operator examples

u64& u64::operator /= (const u64& v)
{
Divide( *this, v, true );
return *this;
}

u64& u64::operator %= (const u64& v)
{
Divide( *this, v, false );
return *this;
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!