가상 메모리 페이지 정렬

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)); 
} 

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의 거듭 제곱 인 경우 빠른 솔루션은 작동 페이지 크기가 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은 (대부분의 시스템에서 동등하게 -pageSize에 ~pageSize + 1과)이 (즉, 단지 1 비트 세트가) 다음 ~(pageSize - 1)의 전원 인 경우는 여전히 특정 비트 세트를 가지고 있으며, 모든 상위 비트도 설정 얻을 :

예를 들면,도 8에 정렬되고, 그것에 의하여 때문에

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 개 (이 예제에서는)와 모든 2 개보다 큰 제곱을 남겨 둡니다. 그러나 두 개 (1,2,4)의 모든 더 낮은 제곱은 제거됩니다.