C语言位操作技巧 之 二进制取整

    二进制数的特点是 "逢二进一", 因此只要一个二进制数的最低位为0, 不管其他位, 这个二进制数都是2的倍数. 就像十进制中, 10, 110, 9870 都是10的倍数一样.

    取整就是将若干个低位设为0. 比如十进制中, 9870, 要取整到千位, 就是要将个十百位全部置为0, 也就是等价于要把这个数调整为1000的倍数. 

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

    向下取整是取不大于一个数的最大整数, 向上取整是取不小于一个数的最小整数, 四舍五入是如果要取整到第n位, 则判断n-1位的值, 如果该值大于等于5, 则执行向上取整, 否则执行向下取整.

    二进制数取整中不存在四舍五入的情况, 因为二进制位的最大值为1.

二进制向下取整

    要将一个二进制数m向下取整到2的k次幂n的倍数, 只需要一个 位与& 运算即可实现.

    n = m & mask

    其中, mask与m的位数相同且低k位全部为0, 其他位全部为1. 实际上是用了

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

    比如 将 9向下取整到2的3次幂8的倍数, 那么结果为

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

    上面的表达式中, 使用了后缀b表示二进制数.

    向下取整到2的2次幂4的倍数, 则结果为

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

二进制向上取整

     要将一个二进制数m向上取整到2的k次幂n, 麻烦一点

n = (m + ~mask) & mask

1 原理

    mask 的值同向下取整的情况一样. 原理需要分两种情况讨论:

(1) m 恰好是2的k次幂的倍数的情况, 也就是m的低k位都是0, 那么 n = m, 可以不执行如何操作;

(2) m 不是2的k次幂的倍数的情况, 也就是m的低k位不全为0, 那么 n = m & mask + (1 << k) = (m + (1  << k)) & mask.

如果分情况计算, 那么就需要判断m是不是2的k次幂, 这样比较麻烦, 效率也比较低, 所以需要位运算来统一计算这两种情况.

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

对于(1),  m = ...0...0, m + ~mask = ...1...1 不会产生进位, (m + ~mask) & mask 可以看成一个向下取整运算, 结果还是m;

对于(2), 因为~mask的低k位全为1, 而m的低k位不全为0, 所以 m + ~mask 必定会产生对第k + 1位的进位, 再把进位后的结果的低k位舍去, 结果就 等于 (m + (1  << k)) & mask, 即

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

    因此, n = (m + ~mask) & mask 完全等价于分情况计算的方式.

2 例子

    比如 将 9向上取整到2的3次幂8的倍数, 那么结果为

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

    向上取整到2的2次幂4的倍数, 则结果为

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