Вопрос о макросе round_up
https://stackoverflow.com/questions/1010922
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
#define ROUND_UP(N, S) ((((N) + (S) - 1) / (S)) * (S))
С помощью приведенного выше макроса, не мог бы кто-нибудь, пожалуйста, помочь мне разобраться в части "(s) -1", почему это?
а также макросы, такие как:
#define PAGE_ROUND_DOWN(x) (((ULONG_PTR)(x)) & (~(PAGE_SIZE-1)))
#define PAGE_ROUND_UP(x) ( (((ULONG_PTR)(x)) + PAGE_SIZE-1) & (~(PAGE_SIZE-1)) )
Я знаю, что часть "(~(PAGE_SIZE-1)))" обнулит последние пять битов, но в остальном я ничего не понимаю, особенно в том, какую роль играет оператор '&'.
Спасибо,
Решение
В ROUND_UP макрос полагается на целочисленное деление для выполнения работы.Это будет работать только в том случае, если оба параметра являются целыми числами.Я предполагаю, что N должно ли число быть округлено и S это интервал, на который его следует округлить.Это, ROUND_UP(12, 5) должен возвращать 15, так как 15 - это первый интервал из 5, больший, чем 12.
Представьте, что мы округляли в меньшую сторону, а не в большую.В этом случае макрос был бы просто:
#define ROUND_DOWN(N,S) ((N / S) * S)
ROUND_DOWN(12,5) вернул бы 10, потому что (12/5) при целочисленном делении равно 2, а 2*5 равно 10.Но мы делаем не ROUND_DOWN, мы делаем ROUND_UP.Поэтому, прежде чем мы выполним целочисленное деление, мы хотим добавить столько, сколько сможем, без потери точности.Если бы мы добавили S, это сработало бы почти в каждом случае; ROUND_UP(11,5) стало бы (((11+5) / 5) * 5), и поскольку 16/5 при целочисленном делении равно 3, мы получили бы 15.
Проблема возникает, когда мы передаем число, которое уже округлено до указанного кратного. ROUND_UP(10, 5) вернул бы 15, и это неправильно.Итак, вместо добавления S, мы добавляем S-1.Это гарантирует, что мы никогда не будем перекладывать что-то в следующую "корзину" без необходимости.
В PAGE_ макросы имеют отношение к двоичной математике.Для простоты мы представим, что имеем дело с 8-битными значениями.Давайте предположим, что PAGE_SIZE является 0b00100000. PAGE_SIZE-1 является таким образом 0b00011111. ~(PAGE_SIZE-1) является ли тогда 0b11100000.
Двоичный файл & выстроит в линию два двоичных числа и оставит 1 в любом месте, где оба числа имели 1.Таким образом, если x был 0b01100111, операция проходила бы следующим образом:
0b01100111 (x)
& 0b11100000 (~(PAGE_SIZE-1))
------------
0b01100000
Вы заметите, что операция действительно обнулила только последние 5 бит.Вот и все.Но это была именно та операция, которая требовалась для округления до ближайшего интервала PAGE_SIZE.Обратите внимание, что это сработало только потому, что PAGE_SIZE была в точности равна степени 2.Это немного похоже на утверждение, что для любого произвольного десятичного числа вы можете округлить его до ближайшего 100, просто обнулив последние две цифры.Это работает отлично, и это действительно легко сделать, но не сработало бы вообще, если бы вы пытались округлить до ближайшего значения, кратного 76.
PAGE_ROUND_UP делает то же самое, но добавляет на страницу столько, сколько может, прежде чем отрезать ее.Это вроде как то, как я могу округлить до ближайшего кратного 100, добавив 99 к любому числу и тогда обнуление последних двух цифр.(Мы добавляем PAGE_SIZE-1 по той же причине, по которой мы добавили S-1 выше.)
Удачи вам с вашей виртуальной памятью!
Другие советы
Используя целочисленную арифметику, деление всегда округляется в меньшую сторону.Чтобы исправить это, вы добавляете максимально возможное число, которое не повлияет на результат, если исходное число было равномерно делимым.Для числа S это максимально возможное число равно S-1.
Округление в степень 2 является особенным, потому что вы можете сделать это с помощью битовых операций.Кратное 2 всегда будет иметь ноль в нижнем бите, кратное 4 всегда будет иметь ноль в двух нижних битах и т.д.Двоичное представление степени 2 представляет собой один бит , за которым следует набор нулей;вычитание 1 очистит этот бит и установит все биты вправо.Инвертирование этого значения создает битовую маску с нулями в тех местах, которые необходимо очистить.Оператор & очистит эти биты в вашем значении, тем самым округляя значение в меньшую сторону.Тот же трюк с добавлением (PAGE_SIZE-1) к исходному значению приводит к его округлению в большую сторону, а не в меньшую.
Макросы округления страницы предполагают, что `PAGE_SIZE - это степень двойки, например:
0x0400 -- 1 KiB
0x0800 -- 2 KiB`
0x1000 -- 4 KiB
Ценность PAGE_SIZE - 1, следовательно, все это один бит:
0x03FF
0x07FF
0x0FFF
Следовательно, если бы целые числа были 16 битами (вместо 32 или 64 - это экономит мне время на вводе текста), то значение ~(PAGE_SIZE-1) является:
0xFC00
0xFE00
0xF000
Когда вы принимаете значение x (предполагая, неправдоподобно для реальной жизни, но достаточно для целей изложения, что ULONG_PTR является 16-разрядным целым числом без знака) является 0xBFAB, тогда
PAGE_SIZE PAGE_ROUND_DN(0xBFAB) PAGE_ROUND_UP(0xBFAB)
0x0400 --> 0xBC00 0xC000
0x0800 --> 0xB800 0xC000
0x1000 --> 0xB000 0xC000
Макросы округляют в меньшую и большую сторону до ближайшего значения, кратного размеру страницы.Последние пять битов будут обнулены только в том случае, если PAGE_SIZE == 0x20 (или 32).
Основываясь на текущем проекте стандарта (C99), этот макрос не совсем корректен, однако обратите внимание, что для отрицательных значений N результат почти наверняка будет неверным.
Формула:
#define ROUND_UP(N, S) ((((N) + (S) - 1) / (S)) * (S))
Использует тот факт, что целочисленное деление округляет в меньшую сторону для неотрицательных целых чисел и использует S - 1 часть, чтобы заставить его вместо этого округлиться.
Однако при целочисленном делении округляется до нуля (C99, раздел 6.5.5.Мультипликативные операторы, пункт 6).Для отрицательных N, правильный способ "округления" - это:'N / S', ни больше, ни меньше.
Это становится еще более запутанным, если S также допускается отрицательное значение, но давайте даже не будем вдаваться в подробности...(см.: Как я могу гарантировать, что деление целых чисел всегда округляется в большую сторону? для более подробного обсуждения различных неправильных и одного или двух правильных решений)
& делает это таким..ну хорошо, давайте возьмем несколько двоичных чисел.
(with 1000 being page size) PAGE_ROUND_UP(01101b)= 01101b+1000b-1b & ~(1000b-1b) = 01101b+111b & ~(111b) = 01101b+111b & ...11000b = (the ... means 1's continuing for size of ULONG) 10100b & 11000b= 10000b
Итак, как вы можете видеть (надеюсь) Это округляется путем добавления PAGE_SIZE к x, а затем и так, чтобы отменить нижние биты PAGE_SIZE, которые не установлены
