????二進(jìn)制數(shù)的特點是 "逢二進(jìn)一", 因此只要一個二進(jìn)制數(shù)的最低位為0, 不管其他位, 這個二進(jìn)制數(shù)都是2的倍數(shù). 就像十進(jìn)制中, 10, 110, 9870 都是10的倍數(shù)一樣.

????取整就是將若干個低位設(shè)為0.?比如十進(jìn)制中, 9870, 要取整到千位, 就是要將個十百位全部置為0, 也就是等價于要把這個數(shù)調(diào)整為1000的倍數(shù).?

????常用的取整方式是向下取整, 向上取整, 四舍五入.

????向下取整是取不大于一個數(shù)的最大整數(shù), 向上取整是取不小于一個數(shù)的最小整數(shù), 四舍五入是如果要取整到第n位, 則判斷n-1位的值, 如果該值大于等于5, 則執(zhí)行向上取整, 否則執(zhí)行向下取整.

????二進(jìn)制數(shù)取整中不存在四舍五入的情況, 因為二進(jìn)制位的最大值為1.

二進(jìn)制向下取整

????要將一個二進(jìn)制數(shù)m向下取整到2的k次冪n的倍數(shù), 只需要一個 位與& 運(yùn)算即可實現(xiàn).

????n = m & mask

??? 其中, mask與m的位數(shù)相同且低k位全部為0, 其他位全部為1. 實際上是用了

0 & 0 = 0, 0 & 1 = 0的特性, 將低k位全部舍去了.

????比如 將 9向下取整到2的3次冪8的倍數(shù), 那么結(jié)果為

n = m & mask = 1001b & 1000b = 1000b = 8

????上面的表達(dá)式中, 使用了后綴b表示二進(jìn)制數(shù).

? ? 向下取整到2的2次冪4的倍數(shù), 則結(jié)果為

n = m & mask = 1001b & 1100 = 1000b = 8

二進(jìn)制向上取整

?????要將一個二進(jìn)制數(shù)m向上取整到2的k次冪n, 麻煩一點

n = (m + ~mask) & mask

1 原理

????mask?的值同向下取整的情況一樣. 原理需要分兩種情況討論:

(1) m 恰好是2的k次冪的倍數(shù)的情況, 也就是m的低k位都是0, 那么 n = m, 可以不執(zhí)行如何操作;

(2) m 不是2的k次冪的倍數(shù)的情況, 也就是m的低k位不全為0, 那么 n = m & mask + (1 << k) = (m + (1? << k)) & mask.

如果分情況計算, 那么就需要判斷m是不是2的k次冪, 這樣比較麻煩, 效率也比較低, 所以需要位運(yùn)算來統(tǒng)一計算這兩種情況.

????已知 mask 是 1...10...0b的情況, 那么~mask = 0...01...1

對于(1),? m = ...0...0, m + ~mask = ...1...1 不會產(chǎn)生進(jìn)位, (m + ~mask) & mask 可以看成一個向下取整運(yùn)算, 結(jié)果還是m;

對于(2), 因為~mask的低k位全為1, 而m的低k位不全為0, 所以 m + ~mask 必定會產(chǎn)生對第k + 1位的進(jìn)位, 再把進(jìn)位后的結(jié)果的低k位舍去, 結(jié)果就 等于?(m + (1? << k)) & mask, 即

(m + ~mask)?& mask =?(m + (1? << k)) & mask.

????因此,?n = (m + ~mask) & mask 完全等價于分情況計算的方式.

2 例子

????比如 將 9向上取整到2的3次冪8的倍數(shù), 那么結(jié)果為

n = (m? + ~ mask) & mask = (1001b? + 0111b) & 1000b = 11111b & 1000b= 10000b = 16

? ? 向上取整到2的2次冪4的倍數(shù), 則結(jié)果為

n = (m? + ~mask)?&?mask = (1001b + 0011b) & 1100b = 1100b?& 1100b = 1100b = 12

????