1. 基本概念 位运算： 用于对整数类型（int,char, long 等）变量中的 某一位(bit)，或者若干位进行操作。比如: 1) 判断某一位是否为1 2) 只改变其中某一位，而保持其他位都不变。 C/C++语言提供了六种位运算符来进行位运算操作： & 按位与(双目) | 按位或(双目) ^ 按位异或(双目) ~ 按位非(取反)(单目) << 左移(双目) >> ...
C++中的按位运算（与、或、非）
按位与运算（&）
按位与运算就是将两个变量的各个bit进行求 与运算，然后将结果输出
按位或运算（|）
将两个变量的各个bit进行按位求或
按位异或（^）
按位取反（~）
位运算——移位（>> <<）
在c++中，经常会对具体整型数据的位进行操作。例如：要获取整数12（0B1100）在第1位上数值（为0），第2位上数值（为1），第3位上数值（为1）。在此，我使用位操作符中的“&”进行读取。
因为整数中的1，2，4，8（2^n n=0,1,2,3,4.....）用二进制表示分别为0B0001,0B0010,0B0100,0B1000，保证了只有一位为1，其余均为0的特性，可以“过滤”出特殊位置出的数值。1 int i(12); //0x1100
2 int j01 = (12 & 4) / 4; //(0x1100 &...
1的个数
解法 1：
用 n & 1 判断最右边一位是否为 1，右移之后继续判断最右边一位，重复直到 n = 0。时间复杂度为 O(log2n)
#include <iostream>
using namespace std;
int main() {int n = 0b1101, cnt = 0;while (n) {cnt += n & 1;n >>= 1;}cout << cnt << endl;return 0;
}解法 2：
用 n & (n - 1) 可以消去最右边的 1，重复直到 n = 0。时间复杂度为 O(count)，取决于 1 的个数 count，所以这种方法优于第一种。
#include <io...
xor (异或)
如果a、b两个值不相同，则异或结果为1
如果a、b两个值相同，异或结果为0
技巧：
这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法
0 xor 0=0
1 xor 0=1
0 xor 1=1
1 xor 1=0（同为0，异为1）
