虚拟内存页对齐

Question

使用此算法来计算给定地址的页面偏移量。

 //naive solution:
int getAlignedValue(int pageSize, int valueToAlign)
{
    int index = valueToAlign/pageSize;
    return index * pageSize;
}
//faster solution:
int getAlignedValue_Fast(int pageSize, int valueToAlign)
{
    return valueToAlign & (~(pageSize-1));
}

天真的方法简单直观，但更快的解决方案只有在页面大小为2的幂时才有效。例如，

pagesize = 8
address = 30
getAlignedValue(8,30) => 24
getAlignedValue_Fast(8,30) => 24
However, when the pagesize is not a power of 2, such as 10
pagesize = 10
address = 24
getAlignedValue(10,24) => 20
getAlignedValue_Fast(10,24) => 16 //wrong

我的问题是，当页面大小是2的幂，使得valueToAlign & (~(pageSize-1))"碰巧"返回正确的对齐方式时，更快的方法使用什么属性，例如24。换句话说，从一个接一个的比特比较中，我所理解的只是它在某种程度上起了作用，但没有理解它背后的数学

//leading 0s are ignored
pagesize = 8 => 00001000, address = 30 => 00011110
=>
~(pagesize - 1) = ~(00000111) = > 11111000 
=>
 00011110
&11111000
----------
 00011000 = 24

非常感谢。

Answer 1

如果pageSize是2的幂（即，它只有1个比特集），那么~(pageSize - 1)（在大多数系统上相当于~pageSize + 1和-pageSize）仍然具有特定的比特集，并且所有更高的比特也都被设置：

pageSize     = 00001000  // bit k is set
// now the -1 will borrow through all rightmost zeroes and finally reset the 1
pageSize-1   = 00000111  // all bits < k are set
// inverting restores the original 1 and also sets all higher bits
~(pageSize-1)= 11111000  // all bits >= k are set

与之进行AND运算将与pageSize对齐，因为例如，与8对齐意味着没有设置"值小于"8的位。掩模叶8（在本例中）和所有二次幂的较高幂，但所有二次方的较低幂（1、2和4）被去除。