位操作算法 – Backend Site

一个算法

给定一个数，找出下一个比它大且值为1的位元数与之相同的数字。算法作用：当用位串表示子集时，比如某位为1就表示某个元素再子集中，此算法可以用来找出元素个数为一定值的全部字集.

举例：假设待计算位串是xxx0 1111 0000 那么下一个比它大且值为1的位元个数相同的数字应是 xxx1 0000 01111.

step1：保留最右侧位元为1的值，并将其他位元置0，此时s=xxx0 0001 0000

s=x&-x

step2: 计算结果中最靠左的一个位元, 此时r= xxx1 0000 0000

r=s+x

step3: 把x位串中剩余的n-1个1移到右侧去，要求首先计算r和x的异或值. 但是异或后结果中的1太多了，而且需要向右靠齐，这要求除以s。但是除以s之前需要先向右移2位以便丢弃那2个多余的位元。
为什么是2个多余的位元，因为(x^r)的结果中有n+1个值位1的位元, 我们目前只需要n-1个值为1的位元移到右侧去。

y= r|(((x^r)>>2)/s)

综上：计算下一个比它大且位元位1的个数相同的数字的算法为：

s=x&(-x)
r=s+x
y= r|(((x^r)>>2)/s)

读到这里你是不是也向我一样对 x&(-x) 一脸懵呢？下面介绍一下位元操作的基本知识。

位操作的基本知识

将x中值为1且最靠右的一位置0. 例如(0101 1110 $\Longrightarrow$ 0101 1100)

x&(x-1)

将x中值为0且最靠右的一位置1.例如(1010 0111 $\Longrightarrow$ 1010 1111)

x|(x+1)

将x中尾部的1都变成0, 如果尾部没有1，则x不变.例如(1010 0111 $\Longrightarrow$ 1010 0000)

x&(x+1)

将x中尾部的0都变成1，如果尾部没有0，则x不变. 例如(1010 1000 $\Longrightarrow$ 1010 1111)

x|(x-1)

将x中最靠右且值为0的位元变为1，并将其余位元置0. 如果x中没有值为0的位元，则结果为0.例如(1010 0111 $\Longrightarrow$ 0000 1000)

~x&(x+1)

将x中最靠右且值为1的位元变为0，并将其余位元置为1. 如果x中没有值为1的位元，则结果中每个位元都是1. 例如(1010 1000 $\Longrightarrow$ 1111 0111)

~x|(x-1)

将x中尾部所有值为0的位元变成1，并将其余位置置成0. 如果x中没有值为0的位元，则结果是0. 例如(0101 1000 $\Longrightarrow$ 0000 0111)

~x&(x-1)

将x中尾部所有值为1的位元都变成0，并将其余位置成1. 如果x中没有值位1的位元，则结果中每个位元都是1. 例如(1010 0111 $\Longrightarrow$ 1111 1000)

~x|(x+1)

将x中最靠右且值位1的位元保留，并将其余位元置0. 若x中不存在值为1的位元，则结果为0. 例如(0101 1000 $\Longrightarrow$ 0000 1000)

x&(-x)

将x中最靠右且值为1的位元及其右方所有值为0的位元都变成1，并将左方位元置0.
若x中没有值为1的位元，则运算结果每一位都为1，当x尾部没有值为0的位元时，运算结果为1. 例如(0101 1000 $\Longrightarrow$ 0000 1111)

x^(x-1)

将x中最靠右且值为0的位元及其右方所有值为1的位元都变成0，并将左方置0.
若x中没有值为0的位元，则运算结果每一位都为1，当x尾部没有值为1的位元时，运算结果为1. 例如(0101 0111 $\Longrightarrow$ 0000 1111)

x^(x+1)

将x中右侧连续出现值为1的位元置0. 例如(0101 1100 $\Longrightarrow$ 0100 0000)

((x|(x-1))+1)&x

位元操作的几个恒等式：

```
-x=~x+1
  =~(x-1)
```

~x=-x-1

-~x=x+1

```
~-x=x-1
```

x+y=x-~y-1