How to Round Up The Result Of Integer Division

Question

I'm thinking in particular of how to display pagination controls, when using a language such as C# or Java.

If I have x items which I want to display in chunks of y per page, how many pages will be needed?

Answer 1

You'll want to do floating point division, and then use the ceiling function, to round up the value to the next integer.

Answer 2

Another alternative is to use the mod() function (or '%'). If there is a non-zero remainder then increment the integer result of the division.

Answer 3

This should give you what you want. You will definitely want x items divided by y items per page, the problem is when uneven numbers come up, so if there is a partial page we also want to add one page.

int x = number_of_items;
int y = items_per_page;

// with out library
int pages = x/y + (x % y > 0 ? 1 : 0)

// with library
int pages = (int)Math.Ceiling((double)x / (double)y);

Answer 4

For C# the solution is to cast the values to a double (as Math.Ceiling takes a double):

int nPages = Math.Ceiling((double)nItems / (double)nItemsPerPage);

In java you should do the same with Math.ceil().

Answer 5

Found an elegant solution:

int pageCount = (records + recordsPerPage - 1) / recordsPerPage;

Source: Number Conversion, Roland Backhouse, 2001

Answer 6

The integer math solution that Ian provided is nice, but suffers from an integer overflow bug. Assuming the variables are all int, the solution could be rewritten to use long math and avoid the bug:

int pageCount = (-1L + records + recordsPerPage) / recordsPerPage;

If records is a long, the bug remains. The modulus solution does not have the bug.

Answer 7

Converting to floating point and back seems like a huge waste of time at the CPU level.

Ian Nelson's solution:

int pageCount = (records + recordsPerPage - 1) / recordsPerPage;

Can be simplified to:

int pageCount = (records - 1) / recordsPerPage + 1;

AFAICS, this doesn't have the overflow bug that Brandon DuRette pointed out, and because it only uses it once, you don't need to store the recordsPerPage specially if it comes from an expensive function to fetch the value from a config file or something.

I.e. this might be inefficient, if config.fetch_value used a database lookup or something:

int pageCount = (records + config.fetch_value('records per page') - 1) / config.fetch_value('records per page');

This creates a variable you don't really need, which probably has (minor) memory implications and is just too much typing:

int recordsPerPage = config.fetch_value('records per page')
int pageCount = (records + recordsPerPage - 1) / recordsPerPage;

This is all one line, and only fetches the data once:

int pageCount = (records - 1) / config.fetch_value('records per page') + 1;

Answer 8

For records == 0, rjmunro's solution gives 1. The correct solution is 0. That said, if you know that records > 0 (and I'm sure we've all assumed recordsPerPage > 0), then rjmunro solution gives correct results and does not have any of the overflow issues.

int pageCount = 0;
if (records > 0)
{
    pageCount = (((records - 1) / recordsPerPage) + 1);
}
// no else required

All the integer math solutions are going to be more efficient than any of the floating point solutions.

Answer 9

Note that rjmunro's solution of:

pageCount = (records - 1) / recordsPerPage + 1

does not fail for records=0 in languages that round negative integers away from zero, such as Python.

Answer 10

Alternative to remove branching in testing for zero:

int pageCount = (records + recordsPerPage - 1) / recordsPerPage * (records != 0);

Not sure if this will work in C#, should do in C/C++.

Answer 11

A generic method, whose result you can iterate over may be of interest:

public static Object[][] chunk(Object[] src, int chunkSize) {

    int overflow = src.length%chunkSize;
    int numChunks = (src.length/chunkSize) + (overflow>0?1:0);
    Object[][] dest = new Object[numChunks][];      
    for (int i=0; i<numChunks; i++) {
        dest[i] = new Object[ (i<numChunks-1 || overflow==0) ? chunkSize : overflow ];
        System.arraycopy(src, i*chunkSize, dest[i], 0, dest[i].length); 
    }
    return dest;
}