关于round_up宏的问题

Question

#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)))"部分会将最后五位归零,但除此之外我无能为力,尤其是角色'&'运算符.

谢谢,

Answer 1

该ROUND_UP宏依靠整数除法来完成这项工作.它只有在两个参数都是整数时才有效.我假设这N是要舍入的数字,并且S是应该舍入的间隔.也就是说,ROUND_UP(12, 5)应该返回15,因为15是第一个大于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做同样的事情,但它在切断之前尽可能多地添加到页面.这有点像我可以通过向任何数字添加99 然后将最后两位数字归零来舍入到最接近的100的倍数.(我们添加PAGE_SIZE-1的原因与S-1上面添加的原因相同.)

祝你虚拟内存好运!

Answer 2

使用整数算术时，除法总是向下舍入。为了解决这个问题，您可以添加尽可能大的数字，如果原始数字可以整除，则不会影响结果。对于数字 S，最大可能的数字是 S-1。

四舍五入到 2 的幂很特殊，因为您可以通过位运算来完成。2 的倍数在底部位中总是有一个零，4 的倍数在底部两位中总是有零，等等。2 的幂的二进制表示形式是一个位后面跟着一堆零；减 1 将清除该位，并将所有位设置为右侧。反转该值会创建一个位掩码，其中需要清除的位置为零。& 运算符将清除值中的这些位，从而将值向下舍入。将 (PAGE_SIZE-1) 添加到原始值的相同技巧会导致它向上舍入而不是向下舍入。