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

## 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 on other sites
No, but I would highly suggest you use long long or some compiler-dependant 64-bit type, instead.

##### Share on other sites
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 on other sites
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 on other sites
Quote:
 Original post by CatafriggmNo, 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 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 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 on other sites
typedef unsigned __int64 ulong64;

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

##### Share on other sites

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 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 examplesu64& u64::operator /= (const u64& v){    Divide( *this, v, true );    return *this;}u64& u64::operator %= (const u64& v){    Divide( *this, v, false );    return *this;}

1. 1
Rutin
41
2. 2
3. 3
4. 4
5. 5

• 16
• 18
• 12
• 14
• 9
• ### Forum Statistics

• Total Topics
633360
• Total Posts
3011524
• ### Who's Online (See full list)

There are no registered users currently online

×