Как округлить результат целочисленного деления?
Я думаю, в частности, о том, как отображать элементы управления разбиением на страницы при использовании такого языка, как C# или Java.
Если у меня есть элементы Икс, которые я хочу отображать кусками по y на страницу, сколько страниц потребуется?
@rikkit - если y и x равны, y / x + 1 слишком велико.
Для тех, кто только что обнаружил это, этот ответ на дурацкий вопрос позволяет избежать ненужного преобразования в double и позволяет избежать проблем с переполнением в дополнение к предоставлению четкого объяснения.
@IanNelson в целом, если x делится на y, y/x + 1 будет слишком большим.
@ ZX9 Нет, это не позволяет избежать проблем с переполнением. Это точно такое же решение, которое опубликовал здесь Ян Нельсон.
Ответы 16
Вы захотите выполнить деление с плавающей запятой, а затем использовать функцию потолка, чтобы округлить значение до следующего целого числа.
Другой альтернативой является использование функции mod () (или «%»). Если есть ненулевой остаток, увеличьте целочисленный результат деления.
Это должно дать вам то, что вы хотите. Вам определенно понадобится x элементов, разделенных на y элементов на странице, проблема в том, что появляются нечетные числа, поэтому, если есть неполная страница, мы также хотим добавить одну страницу.
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);
x / y + !! (x% y) избегает ветвления для C-подобных языков. Шансы хорошие, но ваш компилятор все равно это делает.
+1 для того, чтобы не переполняться, как в ответах выше ... хотя преобразование int в удвоение только для Math.ceiling, а затем обратно - плохая идея в коде, чувствительном к производительности.
@RhysUlerich, который не работает в C# (не может напрямую преобразовать int в bool). Думаю, решение rjmunro - единственный способ избежать ветвления.
Для C# решением является приведение значений к двойному (поскольку Math.Ceiling принимает двойное значение):
int nPages = (int)Math.Ceiling((double)nItems / (double)nItemsPerPage);
В java вы должны сделать то же самое с Math.ceil ().
почему этот ответ так далеко вниз, когда оператор явно запрашивает C#!
Вам также необходимо преобразовать вывод в int, потому что Math.Ceiling возвращает double или decimal, в зависимости от типов ввода.
потому что это крайне неэффективно
Это может быть неэффективно, но это очень легко понять. Учитывая, что подсчет количества страниц обычно выполняется один раз за запрос, никакая потеря производительности не поддается измерению.
Едва ли более читабельно, чем это "(делимое + (делитель - 1)) / делитель;" также он медленный и требует математической библиотеки.
@rolls Я думаю, что под «читабельным» он имел в виду, что внимание намного яснее.
Нашел элегантное решение:
int pageCount = (records + recordsPerPage - 1) / recordsPerPage;
Источник: Преобразование чисел, Роланд Бэкхаус, 2001
-1 из-за ошибки переполнения, указанной Брэндон Дюретт
Мистер Очевидный говорит: не забудьте убедиться, что значение recordsPerPage не равно нулю.
Хорошая работа, не могу поверить, что в C# нет целочисленного потолка.
Ага, вот в середине 2017 года я натыкаюсь на этот отличный ответ, попробовав несколько более сложных подходов.
Для языков с правильным оператором евклидова деления, таких как Python, еще более простым подходом будет pageCount = -((-records) // recordsPerPage).
+1, потому что это также работает с числами без знака (актуально для других языков): «Упрощение» (records - 1) / recordsPerPage + 1 не работает, когда записи == 0.
Целочисленное математическое решение, которое предоставил Ян, неплохо, но страдает ошибкой целочисленного переполнения. Предполагая, что все переменные - int, решение можно переписать, чтобы использовать математику long и избежать ошибки:
int pageCount = (-1L + records + recordsPerPage) / recordsPerPage;
Если records - это long, ошибка остается. В модульном решении нет ошибки.
Я не думаю, что вы реально столкнетесь с этой ошибкой в представленном сценарии. 2 ^ 31 запись - это довольно много, чтобы пролистать страницу.
@rjmunro, реальный пример здесь
@finnw: AFAICS, на этой странице нет реального примера, просто отчет о том, что кто-то другой обнаружил ошибку в теоретическом сценарии.
@rjmunro, я имел в виду это: «Я столкнулся с этой странностью, когда работал над программой просмотра таблиц на основе SWT, которая поддерживает разбиение на страницы. Внутренне программа просмотра таблиц использует Lists.partition () для разделения своих входных элементов на страницы фиксированного размера».
Да, я педантично указывал на ошибку. Многие ошибки могут существовать вечно, не вызывая при этом никаких проблем. Ошибка такой же формы существовала в реализации binarySearch в JDK около девяти лет, прежде чем кто-то сообщил о ней (googleresearch.blogspot.com/2006/06/…). Думаю, вопрос в том, почему бы не исправить это заранее, независимо от того, насколько маловероятно, что вы столкнетесь с этой ошибкой?
Кроме того, следует отметить, что имеет значение не только количество выгружаемых элементов, но и размер страницы. Итак, если вы создаете библиотеку, и кто-то решает не листать, передав 2 ^ 31-1 (Integer.MAX_VALUE) в качестве размера страницы, то возникает ошибка.
Преобразование в числа с плавающей запятой и обратно кажется огромной тратой времени на уровне процессора.
Решение Яна Нельсона:
int pageCount = (records + recordsPerPage - 1) / recordsPerPage;
Можно упростить до:
int pageCount = (records - 1) / recordsPerPage + 1;
AFAICS, у этого нет ошибки переполнения, на которую указал Брэндон Дюретт, и поскольку он использует ее только один раз, вам не нужно хранить RecordsPerPage специально, если он исходит от дорогостоящей функции для извлечения значения из файла конфигурации или что нибудь.
Т.е. это может быть неэффективно, если config.fetch_value использовал поиск в базе данных или что-то в этом роде:
int pageCount = (records + config.fetch_value('records per page') - 1) / config.fetch_value('records per page');
Это создает переменную, которая вам действительно не нужна, которая, вероятно, имеет (незначительные) последствия для памяти и просто слишком много печатает:
int recordsPerPage = config.fetch_value('records per page')
int pageCount = (records + recordsPerPage - 1) / recordsPerPage;
Это все одна строка, и данные извлекаются только один раз:
int pageCount = (records - 1) / config.fetch_value('records per page') + 1;
+1, проблема с нулевыми записями, по-прежнему возвращающими 1 pageCount, на самом деле удобна, поскольку мне все равно нужна 1 страница, показывающая заполнитель / фальшивую строку «нет записей, соответствующих вашим критериям», помогает избежать любых проблем с «счетчиком 0 страниц» во всем управление разбивкой на страницы, которое вы используете.
Имейте в виду, что два решения не возвращают одно и то же значение pageCount для нулевых записей. Эта упрощенная версия возвращает 1 pageCount для нулевых записей, тогда как версия Roland Backhouse возвращает 0 pageCount. Хорошо, если вы этого хотите, но эти два уравнения не эквивалентны при выполнении целочисленным делением в стиле C# / Java.
крошечное редактирование для ясности для людей, просматривающих его и отсутствующих бодм при переходе на упрощение из решения Нельсона (как я сделал в первый раз!), упрощение с помощью скобок ... int pageCount = ((records - 1) / recordsPerPage) +1;
Вы должны добавить скобки к упрощенной версии, чтобы она не зависела от определенного порядка операций. то есть ((записи - 1) / recordsPerPage) + 1.
Кроме того, это проще перевести на другие задачи деления; Полезно знать, что есть простой способ разделить потолок целыми числами.
@Ian, этот ответ НЕ ВСЕГДА возвращает 1. Он может возвращать 0, если ваш recordsPerPage равен «1» и есть 0 записей: -1 / 1 + 1 = 0. Хотя это не очень распространенное явление, важно помнить о том, разрешаете ли вы пользователям изменять размер страницы. Поэтому либо не разрешайте пользователям иметь размер страницы 1, либо проверьте размер страницы, либо и то, и другое (вероятно, предпочтительнее, чтобы избежать неожиданного поведения).
Однако это не решение проблемы переполнения. С решением Яна вы получаете вдвое больший полезный диапазон, если используете целые числа без знака, а records + recordsPerPage имеет верхнюю границу 2 ^ 32 или 2 ^ 64. С помощью этого решения вы можете использовать только целое число со знаком для records, иначе оно будет переполняться на 0 - 1, поэтому records имеет верхнюю границу 2 ^ 31 или 2 ^ 63.
FWIW, я делал что-то подобное, вычисляя максимальное количество страниц, и если номера страниц начинаются с 0, это становится красивым, чистым ... maxPage = (records - 1) / recordsPerPage. Единственная проблема в том, что у него такая же проблема, когда records == 0 ... если recordsPerPage равно 1, результат будет -1 (чего бы я хотел), но если recordsPerPage> 1, вы получите 0.
Для записей == 0 решение rjmunro дает 1. Правильное решение - 0. Тем не менее, если вы знаете, что записи> 0 (и я уверен, что мы все предположили, что recordsPerPage> 0), тогда решение rjmunro дает правильные результаты и не имеет проблем с переполнением.
int pageCount = 0;
if (records > 0)
{
pageCount = (((records - 1) / recordsPerPage) + 1);
}
// no else required
Все целочисленные математические решения будут более эффективными, чем любой решений с плавающей запятой.
Этот метод вряд ли станет узким местом для производительности. А если да, то стоит также учитывать стоимость отделения.
Альтернатива удалению ветвления при тестировании нуля:
int pageCount = (records + recordsPerPage - 1) / recordsPerPage * (records != 0);
Не уверен, что это будет работать на C#, должно работать на C / C++.
Может быть интересен универсальный метод, результат которого вы можете перебирать:
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;
}
Lists.partition(List, int)) and ironically the size() method of the resulting List (as of r09) suffers from the overflow bug mentioned in Ответ Брэндона Дюретта.
Вариант Ответ Ника Берарди, избегающий ветвления:
int q = records / recordsPerPage, r = records % recordsPerPage;
int pageCount = q - (-r >> (Integer.SIZE - 1));
Примечание. (-r >> (Integer.SIZE - 1)) состоит из знакового бита r, повторяемого 32 раза (благодаря знаковому расширению оператора >>). Он оценивается как 0, если r равен нулю или отрицательный, и -1, если r положительный. Таким образом, вычитание его из q приводит к добавлению 1, если records % recordsPerPage > 0.
У меня была аналогичная потребность, когда мне нужно было преобразовать минуты в часы и минуты. Я использовал:
int hrs = 0; int mins = 0;
float tm = totalmins;
if ( tm > 60 ) ( hrs = (int) (tm / 60);
mins = (int) (tm - (hrs * 60));
System.out.println("Total time in Hours & Minutes = " + hrs + ":" + mins);
Следующее должно выполнять округление лучше, чем приведенные выше решения, но за счет производительности (из-за вычисления с плавающей запятой 0,5 * rctDenominator):
uint64_t integerDivide( const uint64_t& rctNumerator, const uint64_t& rctDenominator )
{
// Ensure .5 upwards is rounded up (otherwise integer division just truncates - ie gives no remainder)
return (rctDenominator == 0) ? 0 : (rctNumerator + (int)(0.5*rctDenominator)) / rctDenominator;
}
Я делаю следующее, обрабатываю любые переполнения:
var totalPages = totalResults.IsDivisble(recordsperpage) ? totalResults/(recordsperpage) : totalResults/(recordsperpage) + 1;
И используйте это расширение, если результатов нет:
public static bool IsDivisble(this int x, int n)
{
return (x%n) == 0;
}
Кроме того, для текущего номера страницы (не спрашивали, но могут быть полезны):
var currentPage = (int) Math.Ceiling(recordsperpage/(double) recordsperpage) + 1;
При необходимости в методе расширения:
public static int DivideUp(this int dividend, int divisor)
{
return (dividend + (divisor - 1)) / divisor;
}
Никаких проверок здесь (переполнение, DivideByZero и т. д.), Можете добавить, если хотите. Кстати, для тех, кто беспокоится о накладных расходах на вызов методов, простые функции, подобные этой, могут быть встроены компилятором в любом случае, поэтому я не думаю, что об этом следует беспокоиться. Ваше здоровье.
P.S. вам может быть полезно знать об этом (он получает остаток):
int remainder;
int result = Math.DivRem(dividend, divisor, out remainder);
Это неверно. Например: DivideUp(4, -2) возвращает 0 (должно быть -2). Это правильно только для неотрицательных целых чисел, что не ясно из ответа или из интерфейса функции.
Таш, почему бы тебе не сделать что-нибудь полезное, например, добавить небольшую дополнительную проверку, тогда, если число отрицательное, вместо того, чтобы проголосовать за мой ответ, и неправильно сделать общее заявление: «Это неверно», когда на самом деле это просто край дело. Я уже дал понять, что вы должны сначала выполнить другие проверки: «Здесь нет проверок (переполнение, DivideByZero и т. д.), не стесняйтесь добавлять, если хотите».
В вопросе упоминалось: «Я думаю, в частности, о том, как отображать элементы управления разбивкой на страницы», чтобы отрицательные числа в любом случае были за пределами поля. Опять же, просто сделайте что-нибудь полезное и предложите дополнительную проверку, если хотите, это командный человек.
Я не хотел показаться грубым, и мне очень жаль, если вы так считаете. Возник вопрос: «Как округлить результат целочисленного деления». Автор упомянул разбиение на страницы, но у других людей могут быть другие потребности. Я думаю, было бы лучше, если бы ваша функция каким-то образом отражала, что она не работает для отрицательных целых чисел, поскольку это не ясно из интерфейса (например, другое имя или типы аргументов). Для работы с отрицательными целыми числами вы можете, например, взять абсолютное значение делимого и делителя и умножить результат на его знак.
КАК ОКРУГАТЬ РЕЗУЛЬТАТ ЦЕЛОГО ДЕЛЕНИЯ В C#
Мне было интересно узнать, как лучше всего сделать это на C#, так как мне нужно делать это в цикле почти до 100 тысяч раз. Решения, опубликованные другими пользователями, использующими Математика, получают высокие оценки в ответах, но при тестировании я обнаружил, что они медленные. Джарод Эллиотт предложил лучшую тактику проверки того, производит ли мод что-либо.
int result = (int1 / int2);
if (int1 % int2 != 0) { result++; }
Я запускал это в цикле 1 миллион раз, и это заняло 8 мс. Вот код с использованием Математика:
int result = (int)Math.Ceiling((double)int1 / (double)int2);
В моем тестировании частота составила 14 мс, что значительно дольше.
Я что-то пропустил? y / x + 1 отлично работает (при условии, что вы знаете, что оператор / всегда округляет в меньшую сторону).