Cheatsheet: Bitwise 操作

如果遇到看不懂的,可以到 BitwiseCmd 动手试试。

高位清零

v & ( (1 << WIDTH) - 1 ),则大于等于 WIDTH 的位都将清零。

v & ( (1 << WIDTH + 1) - 1 ),则限定最大宽度为 WIDTH。大于 WIDTH 的位都将清零。

例子:

1var PA_WIDTH_SV39 = 56 // 7 oct
2var v = 0x76543210
3var ret = v & ( (1 << PA_WIDTH_SV39) - 1 )
4ret.toString(16)
5---------------------------
6out: 543210

上下对齐

例子:4K 向下对齐

1var PAGE_SIZE = 4096 // 12 bit
2var PAGE_SIZE_BIT = Math.log(PAGE_SIZE)/Math.log(2)
3var v = 0x12345678
4var ret = v >> PAGE_SIZE_BIT << PAGE_SIZE_BIT
5ret.toString(16)
6---------------------------
7out: 12345000

例子:4K 向上对齐

1var PAGE_SIZE = 4096 // 12 bit
2var PAGE_SIZE_BIT = Math.log(PAGE_SIZE)/Math.log(2)
3var v = 0x12345678
4var ret = (v + PAGE_SIZE - 1) >> PAGE_SIZE_BIT << PAGE_SIZE_BIT
5ret.toString(16)
6---------------------------
7out: 12346000

例子:取 4K 对齐的页框号:

1impl PhysAddr {
2    pub fn floor(&self) -> PhysPageNum { PhysPageNum(self.0 / PAGE_SIZE) }
3    pub fn ceil(&self) -> PhysPageNum { PhysPageNum((self.0 + PAGE_SIZE - 1) / PAGE_SIZE) }
4}

取低位

1var PAGE_SIZE_BIT = 12
2var v = 0x12345678
3var ret = v & ((1 << PAGE_SIZE_BIT) - 1)
4ret.toString(16)
5---------------------------
6out: 678

例子:取页内偏移

1    pub fn page_offset(&self) -> usize {
2        self.0 & (PAGE_SIZE - 1) // PAGE_SIZE = 4096
3    }

x & -x 求 x 最低位置的 1 位代表的数字

 1下面的数,最低位的 1 就在最末尾,因此代表的数字是 1
 2>12345&-12345
 3  12345 00000000000000000011000000111001  0x3039
 4& -12345  11111111111111111100111111000111  -0x3039
 5= 1 00000000000000000000000000000001  0x1
 6
 7下面的数,最低的 1 位在倒数第二个位置,代表的数字是二进制的 10
 8>0x32&-0x32
 9  0x32  00000000000000000000000000110010  50
10& -0x32 11111111111111111111111111001110  -50
11= 0x2 00000000000000000000000000000010  2
12
13下面的数,最低的 1 位在倒数第 8 个位置,代表的数字是二进制的 1000 0000
14>128&-128
15  128 00000000000000000000000010000000  0x80
16& -128  11111111111111111111111110000000  -0x80
17= 128 00000000000000000000000010000000  0x80
18
19>22&-22
20  22  00000000000000000000000000010110  0x16
21& -22 11111111111111111111111111101010  -0x16
22= 2 00000000000000000000000000000010  0x2

x & (x - 1) 抹掉 x 最低位置的 1

 128 的二进制是 00011100,抹掉最后一个 1 得到 00011000
 2>28 & 27
 3  28  00011100  0x1c
 4& 27  00011011  0x1b
 5= 24  00011000  0x18
 6
 729 的二进制是 00011101,抹掉最后一个 1 得到 00011100
 8>29 & 28
 9  29  00011101  0x1d
10& 28  00011100  0x1c
11= 28  00011100  0x1c
12
13>30 & 29
14  30  00011110  0x1e
15& 29  00011101  0x1d
16= 28  00011100  0x1c
17
18>31 & 30
19  31  00011111  0x1f
20& 30  00011110  0x1e
21= 30  00011110  0x1e
22
23>32 & 31
24  32  00100000  0x20
25& 31  00011111  0x1f
26= 0 00000000  0x0

例子:统计数据有多少个 1

1  auto count1 = [](int n) {
2    int c = 0;
3    while (n) {
4      c++;
5      n = n & (n - 1);
6    }
7    return c;
8  };
9  std::cout << count1(-1) << std::endl; // 32

例子:判断数据是否是 $2^n$

1  auto ispow2n = [](int x) {
2    return (x & (x - 1)) == 0;  // 只含有一个 1
3  };
4  std::cout << ispow2n(32) << std::endl; // 1
5  std::cout << ispow2n(1 << 10) << std::endl; // 1
6  std::cout << ispow2n(233) << std::endl; // 0

x & 0x7FFFFFFF 消除符号位

结果一定是正数

1  -0x123123 11111111111011011100111011011101  -1192227
2& 0x7fffffff  01111111111111111111111111111111  2147483647
3= 0x7fedcedd  01111111111011011100111011011101  2146291421

x & 1 == 0 判断奇偶

  • 奇数满足 x & 1 != 0

  • 偶数满足 x & 1 == 0

综合运用

将整数向上扩展到 $2^n$

1  auto up = [](int sz) {
2    // 扩展为满二叉树
3    while (sz & (sz - 1))
4      sz += sz & -sz;
5    return sz;
6  };
7  std::cout << up(23) << std::endl; // 32