一. 概念定义

1.1 位或定义

  按位或 |：是对二进制进行比较，对两个数的二进制的每一位进行，判断方式和 逻辑或 || 一样，一个1 | 1，1 | 0 都为1，0 | 0为0。

例如：
2 | 3；
010 （2的二进制）
011 （3的二进制）
011 （结果）

1.2 位与定义

  按位与 &：按位与也是进行一个二进制的比较，它的比较形式则与 | 相反，0 & 0 和 0 & 1 都为0，1 & 1 为 1。

例如：
2 | 3；
010
011
010

二. 推荐专栏

《算法零基础100讲》(第44讲) 位运算 (位或) 入门

三. 相关练习

3.1 根据数字二进制下 1 的数目排序

题目链接：
根据数字二进制下 1 的数目排序

思路分析：

我们可以定义一个数组bit用于记录arr每个数二进制形式1的个数，如何根据bit对arr进行排序。

代码如下：

int* bit;int get(int n){int cnt = 0;while(n){cnt += (n % 2);n /= 2;}return cnt;
}int cmp(const void* a, const void* b){int x = *(int*)a;int y = *(int*)b;return bit[x] == bit[y] ? x - y : bit[x] - bit[y];
}int* sortByBits(int* arr, int arrSize, int* returnSize){bit = (int*)malloc(sizeof(int) * 10001);memset(bit, 0, sizeof(bit));for(int i = 0; i < arrSize; i++){bit[arr[i]] = get(arr[i]);}qsort(arr, arrSize, sizeof(int), cmp);*returnSize = arrSize;return arr;
}

3.2 二进制表示中质数个计算置位

题目链接：

762. 二进制表示中质数个计算置位

思路分析：

我们对区间 [left，right] 进行遍历，对该区间内的每个数的二进制形式1的个数进行判断，如果为质数，则++，统计所有1的个数为质数的数量。

代码如下：

bool judge(int n){if(n < 2)return false;for(int i = 2; i * i <= n; i++){if(n % i == 0)return false;}return true;
}int countPrimeSetBits(int left, int right){int ans = 0;for(int i = left; i <= right; i++){int cnt = 0;int kk = i;while(kk){kk = kk & (kk - 1);//计算1的个数cnt++;}if(judge(cnt)){ans++;}}return ans;
}

3.3 2 的幂

题目链接：
231. 2 的幂

思路分析：

通过循环计算2的幂，幂是多少就循环多少次。

代码如下：

bool isPowerOfTwo(int n){if(n == 1){return true;}long long t = 2;while(t != n){t *= 2;if(t > n){return false;}}return true;
}