Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1303
  • Last Modified:

divide ULONGLONG ?

Cfile::GetLength() returns a ULONGLONG.

I need to divide this value... how do i do it???


c = a/b;

How do i cope with the insane amount of bits?? :D

1 Solution
This is the definition of a LONGLONG (similar for ULONGLONG)

typedef union _LARGE_INTEGER {
  struct {
     DWORD LowPart;
     LONG  HighPart;
  LONGLONG QuadPart;

The following is an example of how to manipule large numbers, you can beautify the multiplication by 4294967296 if you want using arithmetic shift or any other way but it is not the main issue.

  // as we work with very large numbers we need to divide the number before we make
  // mathematical manipulation with them
  // we return a percentage.
  short space_on_disk(string drive_path)
    ULARGE_INTEGER freeBytesAvailableToCaller;
    ULARGE_INTEGER totalNumberOfBytes;
    ULARGE_INTEGER totalNumberOfFreeBytes;

    if (!GetDiskFreeSpaceEx(drive_path.c_str(),  
       throw IOError("space_on_disk");
    unsigned __int64 i;
    unsigned __int64 j;

    i = totalNumberOfFreeBytes.LowPart;
    j = totalNumberOfFreeBytes.HighPart * 4294967296;

    __int64 m = j + i;

    i = totalNumberOfBytes.LowPart;
    j = totalNumberOfBytes.HighPart * 4294967296;

    __int64 n = j + i;

    return short((m / 100) / (n / 10000));

Hope this helps
Actually ULONGLONG is fine.

Most modern compilers provide a 64 bit integer.

GNU GCC C++ and C compilers use the name

long long x; // signed 64 bit integer
unsigned long long x; // unsigned 64 bit integer

MSVC and Borland C++ builder uses the names

__int64 x; // signed 64 bit integer
unsigned __int64 x; // unsigned 64 bit integer.

To make code that works on both compilers you are adviced to make a typedef which goes something like this:

#if _GNU_
typedef long long int64_t;
typedef unsigned long long uint64_t;
#else // assume MSVC or BCB
typedef __int64 int64_t;
typedef unsigned __int64 uint64_t;

If you have something that is neither GNU, nor MSVC, nor Borland C++ builder but it also provide a 64 bit integer you just have to make the #if a bit more fancy.

Then the question about dividing the values are simply:

uint64_t a;
uint64_t b;
uint64_t c = a / b;

All those compilers provide support for +, -, *, / and % on 64 bit integer data types both signed and unsigned.

What if your compiler do NOT provide support but you still want to do it? what then?

Easy enough:

Step 1. define a struct to hold the data:

struct uint64_t {
   unsigned int low;
   unsigned int high;

You might want to switch 'low' and 'high' if you're on a machine with different endianess than a pentium processor.

Then the answer is simply:

uint64_t operator / (const uint64_t & a, const uint64_t & b);

For the body of this function the following must be kept in mind:

A 64 bit value represented as two 32 bit values is simply:

V = H * R + L

Here V is the value of the 64 bit integer.
H is the high 32 bit part (high in that struct above).
L is the low 32 bit part (low in that struct above).
R is the value pow(2,32) or 2 raised to the power of 32.

If you have two such values A and B, B > 0 then you can find a quotient Q and a remainder R such that:

A = Q * B + R.

0 <= R < B

If Q == QH * R + QL, A == AH * R + AL, B == BH * R + BL and R == RH * R + RL this becomes:

AH * R + AL == (QH * R + QL) * (BH * R + BL) + RH * R + RL

Multiplying out we get:

AH * R + AL = QH * BH * R*R + (QH * BL + QL * BH + RH) * R + (QL * BL + RL)

Since Each value here AH,AL,QH,QL,BH,BL,RH,RL are all such that they are 0 <= val < R it follows that A < R*R and so QH * BH == 0. Thus one of them must be 0.

Thus we have two situations:

BH == 0 or BH != 0

IF BH == 0, B == BL and the division is simply done like this:

Divide a 64 bit unsigned integer with a 32 bit unsigned integer.

Most computers already provide an instruction that does that, if you don't have access to such an instruction you need to resort to multiple precision techniques or splitting the 64 bit value into four 16 bit values. However, this is kinda ugly so unless you state you need that I won't provide it.

If BH != 0 then QH must be 0 and so we get:

AH * R + AL = QL * (BH * R + BL) + RH * R + RL
            = (QL * BH  + RH) * R + (QL * BL + RL)

Here it is clear that AH = QL * BH + RH + (QL * BL + RL)/R.

If you do a AH,AL / BH. I.e. a 64 bit unsigned integer divided by a 32 bit unsigned integer you get a quotient q and remainder r. The quotient q is close to QL but might be off by some amount. If q >= R set q = R - 1. Under no circumstance should q be greater or equal to R.

You find out how much it is off by doing:

q * B == q * (BH * R + BL) == (q * BH) * R + (BL * q)
      == (q * BH + (BL*q)/R) * R + (BL * q) % R

doing a long multiplication of q and subtract it from A you get:

A - q * B = pH * R * pL

if q * B is greater than A then q is too large and you should make it smaller and compute the q * B again and subtract again. Repeat this process until q * B is less or equal to A, then you have QL == q and:

q * B is a 32 bit unsigned number q multiplied by a 64 bit unsigned number B (BH * R + BL).

A - QL * B == RH * R + RL

QL is the result of the division.

Since you need to do 32 bit by 64 bit multiplication to do the division you probably need that algorithm as well:

A * (BH * R + BL) == A * BH * R + A * BL
            == (A * BH + (A * BL)/R) * R + (A * BL) % R

so, multiply A * BL, this usually give a 64 bit result if you use machine instructions. The lower 32 bits of this is the lower 32 bits of the result. The upper bits are kept and added to A * BH. This give a 64 bit result so the result value can actually be 96 bits but if you want to keep only the lower 64 bits you just test the upper 32 bits of this high multiplication. If that result is non-zero you flag overflow and if it is zero you drop it and keep only the lower 32 bits of that high multiplication as the high 32 bit of the result (after adding the upper 32 bits of the lower multiplication).

In other words:

Compute A * BL into 64 bits (32 * 32 into 64 result)
the lower 32 bits is the lower 32 bits of result.
The upper 32 bits is kept - we call it x.
Compute A * BH into 64 bits and then add x and store the upper 32 bits in z and the lower 32 bits in y.
If the upper 32 bits (z) is non-zero flag overflow (throw exception or whatever), if z is zero save y into the 32 upper bits of result.

Multiplying two 64 bit values into a 128 bit value is similar:

(AH * R + AL)* (BH * R + BL) ==
   AH * BH * R * R + (AH * BL + AL * BH) * R + AL * BL

I.e. first multiply AL * BL into 64 bits, the low 32 bits are the low 32 bits of result, keep the upper 32 bits into x.

Then multiply AH * BL + AL * BH + x. The low 32 bits are bits 32..63 of result and the upper 32 bits are stored into x.

Then multiply AH * BH + x. The 64 bits are bits 64.127 of the result.

As you can see, the multiplication is several times easier than division.


Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now