位操作运算

运算符

符号	语法	名称	含义
`&`	`a&b`	按位与	均为 `1` 时才是 `1` ，否则是 `0` ；只要有 `0` ，就是 `0`
`\|`	`a\|b`	按位或	均为 `0` 是才是 `0` ，否则是 `1` ；只要有 `1` ，就是 `1`
`^`	`a^b`	按位异或	相同是 `0` ，不同是 `1` ；`1^1=0^0=0`，`1^0=0^1=1`
`~`	`~x`	取反	每一位都取相反数
`<<`	`a<<val`	左移	向左移，不足补 `0` ，多余去除
`>>`	`a>>val`	右移*	向左移，不足补 `0` ，多余去除*

view.jpg | ori.png | ori.svg
alt text

*特别地，对于右移运算：

#include <bits/stdc++.h>
using namespace std;

int main(){
	signed a=9,b=-9;
	printf("%d %d %d %d",a>>1,b>>1,a>>2,b>>2);
	return 0;
	// output: 4 -5 2 -3
}

常用技巧

乘/除以 2 的幂次

除：257>>4 等同于 257/pow(2,4)
乘：3<<4 等同于 3*pow(2,4)
常用 a<<=1 代表 a*=2 ；常用 a>>=1 代表 a/=2 *

#include <bits/stdc++.h>
using namespace std;

int main(){
	printf("%d %d",257>>4,3<<4);
	return 0;
	// output: 16 48
}

*同样地，特别注意右移对于负数的取整方式，负数的左移：

#include <bits/stdc++.h>
using namespace std;

int main(){
	printf("%d %d\n",(-257)>>4,257>>4);
	printf("%d %d",(-3)<<4,3<<4);
	return 0;
	// warning on line 6 colum 21: [警告] left shift of negative value [-Wshift-negative-value]
	/**
	 * output: 
	 * -17 16
	 * -48 48
	 */
}

交换两数

交换两数建议使用 swap() 函数（非常强大），或者定义第三个变量临时存储，较为常用。
使用和差交换或者位运算交换可能会导致溢出，不建议使用。

#include <bits/stdc++.h>
using namespace std;

int main(){
	int a=1,b=2;
	a=a^b; // a^=b;
	b=a^b; // b^=a;
	a=a^b; // a^=b;
	return 0;
}

这里用到的按位异或性质：

相同的数按位异或为 $0$
任何数按位异或 $0$ 都是它本身
按位异或符合交换律、结合律

第7行展开写是 b'=a'^b'=(a^b)^b=a^(b^b)=a^0=a；
第8行展开写是 a'=a'^b'=(a^b)^a=b^(a^a)=b^0=b。
（没带 ' 的是原始变量）

基本例题

判断是否是 2 的幂

力扣链接：231. Power of Two

一个数是 $2$ 的幂，其二进制必须是一个 1 加上若干个 0 ，如 1000 。满足这个数减去 $1$ 后每一位都与原数不同。如对于 $2$ 的 $4$ 次方 $16$ ：

  10000 => 16
& 01111 => 16-1
-------
  00000 => 0

原理可参考#法1 - 按位与运算。

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return (n>0) && (n&(n-1))==0;
    }
};

二进制中 1 的个数

力扣链接：191. Number of 1 Bits

法1 - 按位与运算

与#判断是否是 $2$ 的幂类似，通过语句 a&(a-1) 可以消去这个数二进制最低位的 1 ，以 $14$ 举例：

  011 10 => 14
& 011 01 => 14-1
----- --
  011 00

可以看到，减去 $1$ 后与前面的部分（ 011 ）无关（上下每位都相同），后面的部分每位都上下不同。按位与这两个数会保留前面的部分，后面的部分全部置 0 ，因此涉及到的一个 1 被消为 0 。

因此，可以得出：

消去一个数二进制最右侧的 1 ： a&(a-1)
获取一个数二进制最右侧的 1 ： a&(~a+1) 或 a&(-a)** 或 lowbit(x)

** -a 表示 a 的补码

class Solution {
public:
    int hammingWeight(int n) {
        long long int count = 0;
        while(n) {
            count++;
            n&=(n-1);
        }
        return count;
    }
};

法2 - 每一位判断

每次判断最低位是否为 1 ，并右移移掉最低位，直到移为 $0$ 。

class Solution {
public:
    int hammingWeight(int n) {
        long long int count = 0;
        while(n) {
            count += n&1;
            n>>=1;
        }
        return count;
    }
};

转化成不用位运算的方式：

class Solution {
public:
    int hammingWeight(int n) {
        long long int count = 0;
        while(n) {
            count += n%2;
            n/=2;
        }
        return count;
    }
};

二进制是否 0 1 交替

力扣链接：693. Binary Number with Alternating Bits

每次判断相邻的两位是否是 01 或者 10 。
通过对该数按位与运算 $3$ 即可（ $3$ 对应的二进制为 11 ）。如果该数最后两位为 10 ，则按位与结果为 10 ；最后两位为 01 ，则按位与结果为 01 。否则都不满足。
然后把该数右移 $1$ 位，继续检查最后两个二进制位。

class Solution {
public:
    bool hasAlternatingBits(int n) {
        while(n) {
            if((n&3)!=2 && (n&3)!=1)
                return false;
            n>>=1;
        }
        return true;
    }
};

练习题