выравнивание страницы виртуальной памяти

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 это сила два (т.е. он имеет только один набор битов), то ~(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 

И-тов с тем, что выравнивание по pageSize, потому что, например, выровнены по 8 означает, что никакие биты, которые «стоит меньше», чем 8 установлены. Маска оставляет 8 (в этом примере) и всех высших степеней двух, но все нижние степени двух (1, 2 и 4) удаляются.