Custom unsigned int (64 bit) divide
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.
No, but I would highly suggest you use long long or some compiler-dependant 64-bit type, instead.
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 ^_^.
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.
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.
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.
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.
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.
Okay I think I remember it:
Say we are solving a / b
I think that will work. It's untested so there's probably a few off-by-one errors in there.
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.
typedef unsigned __int64 ulong64;
ulong64 a=23804523582523535235;
ulong64 result = a / 8523523532;
ulong64 a=23804523582523535235;
ulong64 result = a / 8523523532;
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.
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.
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;}
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement