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