时间戳

首页 > 解决方案 > 有人可以解释这些代码行在做什么吗？

c++ - 有人可以解释这些代码行在做什么吗？

问题描述

int64_t lstbt(int64_t val){ 
   int64_t msk = val&(val-1); 
   return log2(val^msk);
}

实际计算的是什么msk，为什么我们要返回logvalue xor msk？

标签： c++bit-manipulationbitbitmask

解决方案

理解函数：

int64_t lstbt(int64_t val){ 
   int64_t msk = val&(val-1); 
   return log2(val^msk);
}

让我们把它分成更小的块。

首先声明val-1，通过添加-1，val您翻转（以及其他）最低有效位（LSB），（即 0变成1，反之亦然）。

下一个操作 ( val&(val-1)) 按位应用“与”。从&运营商我们知道：

1 & 1  -> 1
1 & 0  -> 0
0 & 1  -> 0
0 & 0  -> 0

所以要么

  1. val最初是...0，并且val - 1是 ....1，在这种情况下val&(val-1)产生 ...0;

  2. orvar最初是...1, 并且var - 1是 ....0, 在这种情况下val&(val-1)产生 ...0;.

所以在这两种情况下，都val&(val-1)设置0为LSBof var。除此之外，另一个重要的变化val&(val-1)是将0最右边的第一个位设置为1.

所以让我们说 val = xxxxxxxx 1 0000 （xxxxxxxxx1000只要它显示最右边的位设置为 1 就可以了），msk=val&(val-1)那么什么时候msk会是xxxxxxxx00000

接下来，我们有val ^ msk；按XOR位运算，我们知道：

1 ^ 1  -> 0
1 ^ 0  -> 1
0 ^ 1  -> 1
0 ^ 0  -> 0

因此，因为val将类似于xxxxxxxx10000和 msk xxxxxxxx00000，其中用 'x' 表示的位val将与 from 完全匹配msk；的结果 val ^ msk将始终是一个所有位都设置为的数字，0唯一的例外是和bit之间不同，即最右边的位设置为of 。valmsk1val

因此，结果 from val ^ msk将始终是 2 的幂（val0 除外）。一个可以用 表示的值2^y = x，其中y是 中设置为 1 的最右边位的索引val，并且x是 的结果val^msk。因此，log2(val^msk)返回y 即最右边位的索引设置为 1 in val。

推荐阅读