2013-11-21 75 views
1

通過此算法來計算給定地址的頁面偏移量。虛擬內存頁面對齊

//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))「碰巧」返回正確的對齊,例如換句話說,從一點一點地比較比較,我所理解的只是它以某種方式起作用,但沒有理解它背後的數學。

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

非常感謝。

回答

0

如果pageSize是兩個(即,它只有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-ING對齊到pageSize,因爲,例如,被對齊到8表示沒有比特是「值得小於」 8被設置。蒙版離開8(在這個例子中)和所有更高的2的冪,但是所有更低的2(1,2和4)的冪被移除。

+0

謝謝!這是有道理的! –