首页 > 代码库 > 笔记:lowbit()

笔记:lowbit()

因为CodeForces 437B这道题,接触到了lowbit。

先写一下函数:

int lowbit(int x){    return x&(-x);}

以及原题上给出的定义:

lowbit(x) equals 2k where k is the position of the first one in the binary representation of x. For example, lowbit(100102) = 102, lowbit(100012) = 12, lowbit(100002) = 100002 (binary representation).

很易懂,就是二进制形式从右边数到第一个1,该位所代表的2的幂。

函数的原理是计算机的补码,即(假设8位)

1 & -1   0000 0001 & 1111 1111 = 1

4 & -4   0000 0100 & 1111 1100 = 2

5 & -5   0000 0101 & 1111 1011 = 1

 

笔记:lowbit()