位运算最常用的两种操作

看 n 的第 k 位数字是几

一个整数 n, 其二进制表示中第 k 位数字是几, k从 0 开始计数

n=15 ==> n=(1111)~2~

①先把第 k 位移到最后一位: n » k

②看个位是几, 公式是$x&1$

结合①②, 可得要求 n 的二进制第 k 位的公式为: $n » k ;& 1$

对于一个十进制数x, 如果我们从最高位(比如 32 位, 从 k=32)开始打印这个数,那么打印完之后得到的就是x 的二进制表示

lowbit–树状数组基本操作

lowbit(x) : 返回 x 的最后一位 1和后面的二进制数

举例

lowbit(1010~2~) = 10

lowbit(1000~2~) = 1000

lowbit实现方式

$x & -x$

在 c++中, 一个整数的负数是原数的补码(补码是取反加一), 所以 -x 的二进制表示和 ~x+1( x取反加一)的二进制表示是一样的

∵-x = ~x+1

∴x&-x ==> x&(~x+1)

推导过程:


~表示取反

应用

1. 求 x 里面 1的个数

   每次将 x 中的 最后一个 1 减去, 直到x 变为 0, 我们记录减了几次, 就可以知道有多少个 1

   题目:二进制一的个数

原码,反码,补码

令 x=1010~2~ 假设是 32 位整数

原码: 0000…..01010

反码: 0111…..10101 原码除符号位外取反

补码: 0111…..10110 反码加一 ~x+1

为什么要有补码?

因为在计算机里面没有减法, 需要用加法来做减法

一个x 加上他的相反数-x 应该等于 0: x+(-x)=0

那么有如下推导

$(-x) = 0-x\(-x)=(32个 0)_2 - x\此时做减法,32个 0 会往前借一位,也就是\(-x)=(1+后面32个 0)-x\此时\(1+后面32 个 0)-x = \sim{x} + 1\故\减法用\sim{x+1}这个补码表示$

正数和零的原码表示和补码表示是一样的, 不需要专门求补码, 直接用原码表示