Câu hỏi về round_up macro

Question

#define ROUND_UP(N, S) ((((N) + (S) - 1)/(S)) * (S)) 

Với macro ở trên, ai đó có thể giúp tôi hiểu về phần "(s) -1", tại sao vậy?

và các macro như:

#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))) 

tôi biết "(~ (PAGE_SIZE-1)))" phần sẽ không ra năm bit cuối cùng, nhưng khác hơn là tôi tránh khỏi thất bại, đặc biệt là vai trò của nhà điều hành '&'.

Xin cảm ơn,

Answer 1

Macro ROUND_UP dựa vào phân chia số nguyên để hoàn thành công việc. Nó sẽ chỉ hoạt động nếu cả hai tham số là số nguyên. Tôi giả định rằng N là số cần làm tròn và S là khoảng thời gian cần làm tròn. Tức là, ROUND_UP(12, 5) phải trả lại 15, vì 15 là khoảng thời gian đầu tiên của 5 lớn hơn 12.

Hãy tưởng tượng chúng ta làm tròn thay vì lên. Trong trường hợp đó, macro sẽ chỉ đơn giản là:

#define ROUND_DOWN(N,S) ((N/S) * S) 

ROUND_DOWN(12,5) sẽ trở về 10, vì (12/5) trong phân chia số nguyên là 2, và 2 * 5 là 10. Nhưng chúng tôi không làm ROUND_DOWN, chúng tôi đang làm ROUND_UP . Vì vậy, trước khi chúng tôi thực hiện phân chia số nguyên, chúng tôi muốn thêm nhiều nhất có thể mà không làm mất độ chính xác. Nếu chúng tôi thêm S, nó sẽ hoạt động trong hầu hết mọi trường hợp; ROUND_UP(11,5) sẽ trở thành ((((11 + 5)/5) * 5) và từ 16/5 trong phân số nguyên là 3, chúng tôi sẽ nhận được 15.

Sự cố xảy ra khi chúng tôi chuyển một số đã được làm tròn đến đa được chỉ định. ROUND_UP(10, 5) sẽ trả về 15 và điều đó sai. Vì vậy, thay vì thêm S, chúng tôi thêm S-1. Điều này đảm bảo rằng chúng tôi sẽ không bao giờ đẩy thứ gì đó lên "xô" tiếp theo một cách không cần thiết.

Macro PAGE_ phải thực hiện với phép toán nhị phân. Chúng tôi sẽ giả vờ rằng chúng tôi đang xử lý các giá trị 8 bit vì mục đích đơn giản. Giả sử rằng PAGE_SIZE là 0b00100000. PAGE_SIZE-1 là như vậy 0b00011111. ~(PAGE_SIZE-1) sau đó là 0b11100000.

Một số nhị phân & sẽ xếp hai số nhị phân và để 1 ở bất kỳ đâu cả hai số đều có 1.Vì vậy, nếu x là 0b01100111, các hoạt động sẽ đi như thế này:

0b01100111 (x) 
& 0b11100000 (~(PAGE_SIZE-1)) 
------------ 
    0b01100000 

Bạn sẽ lưu ý rằng hoạt động thực sự chỉ zeroed-ra 5 bit cuối cùng. Đó là tất cả. Nhưng đó chính xác là hoạt động cần thiết để làm tròn xuống khoảng thời gian gần nhất là PAGE_SIZE. Lưu ý rằng điều này chỉ làm việc vì PAGE_SIZE chính xác là sức mạnh của 2. Nó giống như nói rằng đối với bất kỳ số thập phân tùy ý nào, bạn có thể làm tròn xuống 100 gần nhất đơn giản bằng cách zero-out hai chữ số cuối cùng. Nó hoạt động hoàn hảo, và thực sự dễ dàng để làm, nhưng sẽ không làm việc ở tất cả nếu bạn đang cố gắng làm tròn đến bội số gần nhất của 76.

PAGE_ROUND_UP cũng làm như vậy, trang trước khi cắt nó đi. Đó là kinda như thế nào tôi có thể làm tròn lên bội số gần nhất của 100 bằng cách thêm 99 cho bất kỳ số nào và sau đó zeroing-out hai chữ số cuối cùng. (Chúng tôi thêm PAGE_SIZE-1 cho cùng một lý do chúng tôi đã thêm S-1 ở trên.)

Chúc bạn may mắn với bộ nhớ ảo!

Answer 2

Sử dụng số học số nguyên, chia luôn làm tròn xuống. Để khắc phục điều đó, bạn thêm số lượng lớn nhất có thể sẽ không ảnh hưởng đến kết quả nếu số ban đầu được chia đều. Đối với số S, con số lớn nhất có thể là S-1.

Làm tròn với sức mạnh của 2 là đặc biệt, bởi vì bạn có thể thực hiện điều đó bằng thao tác bit. Một bội số của 2 sẽ aways có một số không trong bit dưới cùng, một bội số của 4 sẽ luôn luôn có số không trong hai bit dưới, vv Biểu diễn nhị phân của một sức mạnh của 2 là một bit duy nhất theo sau bởi một loạt các số không; trừ 1 sẽ xóa bit đó và đặt tất cả các bit sang phải. Đảo ngược giá trị đó tạo ra một mặt nạ bit với số không ở những nơi cần được xóa. Toán tử & sẽ xóa các bit đó trong giá trị của bạn, do đó làm tròn giá trị xuống. Cùng một mẹo thêm (PAGE_SIZE-1) vào giá trị ban đầu làm cho nó tròn lên thay vì xuống.

Answer 3

& làm cho nó như vậy .. tốt ok, cho phép có một số số nhị phân.

 
(with 1000 being page size) 
PAGE_ROUND_UP(01101b)= 
01101b+1000b-1b & ~(1000b-1b) = 
01101b+111b & ~(111b) = 
01101b+111b & ...11000b = (the ... means 1's continuing for size of ULONG) 
10100b & 11000b= 
10000b 

Vì vậy, như bạn có thể nhìn thấy (hy vọng) này vòng lên bằng cách thêm PAGE_SIZE để x và sau đó ANDing nên hủy bỏ ra các bit dưới cùng của PAGE_SIZE mà không được thiết lập

Answer 4

Các macro trang làm tròn cho rằng 'PAGE_SIZE là một sức mạnh của hai, chẳng hạn như:

0x0400 -- 1 KiB 
0x0800 -- 2 KiB` 
0x1000 -- 4 KiB 

giá trị của PAGE_SIZE - 1, do đó, là tất cả một bit:

0x03FF 
0x07FF 
0x0FFF 

Do đó, nếu số nguyên là 16 bit (thay vì 32 hoặc 64 - nó tiết kiệm cho tôi một số đánh máy), thì giá trị của ~(PAGE_SIZE-1) là:

0xFC00 
0xFE00 
0xF000 

Khi bạn mất giá trị của x (giả sử, implausibly thật cuộc sống, nhưng đủ cho mục đích của triển lãm, mà ULONG_PTR là một unsigned 16-bit integer) là 0xBFAB, sau đó

PAGE_SIZE   PAGE_ROUND_DN(0xBFAB) PAGE_ROUND_UP(0xBFAB) 

0x0400  --> 0xBC00     0xC000 
0x0800  --> 0xB800     0xC000 
0x1000  --> 0xB000     0xC000 

các macro làm tròn xuống và lên đến bội số gần nhất của một kích thước trang. Năm bit cuối cùng sẽ chỉ được lấy ra nếu PAGE_SIZE == 0x20 (hoặc 32).

Answer 5

Dựa trên tiêu chuẩn dự thảo hiện tại (C99), macro này không hoàn toàn chính xác tuy nhiên, lưu ý rằng đối với các giá trị âm của N, kết quả gần như chắc chắn sẽ không chính xác.

Công thức:

#define ROUND_UP(N, S) ((((N) + (S) - 1)/(S)) * (S)) 

Làm cho việc sử dụng thực tế là phân chia số nguyên làm tròn xuống cho các số nguyên không âm và sử dụng phần S - 1 để buộc nó để làm tròn lên thay thế.

Tuy nhiên, số nguyên chia thành 0 (C99, Mục 6.5.5. Toán tử nhân, mục 6). Đối với tiêu cực N, cách chính xác để 'làm tròn' là: 'N/S', không có gì hơn, không có gì ít hơn.

Nó được thậm chí tham gia nhiều hơn nếu S cũng được phép trở thành một giá trị tiêu cực, nhưng chúng ta hãy thậm chí không đến đó ... (xem: How can I ensure that a division of integers is always rounded up? cho một cuộc thảo luận chi tiết hơn về nhiều sai lầm và một hoặc hai giải pháp phù hợp)