目录
剑指 Offer 56 - I. 数组中数字出现的次数 260. 只出现一次的数字 III
剑指 Offer 56 - II. 数组中数字出现的次数 II 137. 只出现一次的数字 II
剑指 Offer 15. 二进制中1的个数 汉明重量 191. 位1的个数
提前阅读：
二进制与位运算实用操作汇总（基础篇）
二进制与位运算实用操作汇总（应用篇）
二进制与位运算实用操作汇总（实战篇）
原创 | 东哥教你几招常用的位运算技巧
常见二进制操作
and 操作，操作符“&”
or 操作，操作符“|”
xor操作，操作符“^”
not操作，操作符“~”
shl操作，操作符“<<”
shr操作，操作符“>>”
and操作
- 判断奇偶数
对于任意数x，使用x&1==1作为逻辑判断，当判断为true时代表x为奇数，否则为偶数。（注意：这样的逻辑会把0当作偶数，注意设置条件判断）
判断某个二进制位是否为1
假如我们要判断第N个二进制位是否为1，可以把1左移N-1位，再进行and操作，如果大于0则代表该二进制位就为1
减去低位的最后一个1
假如我们有一个二进制数 ，当我们想消掉低位的最后一个1时（即此时的第三位），我们可以通过 x&(x-1) 的方式来实现，具体的运算原理如下：
两个整数交换变量名
一般而言，两个变量要交换彼此的值（例如在排序算法中经常要使用这种技巧），都需要借助第三个变量作用临时变量。而如果使用了xor操作，能在不用第三个临时变量的情况下实现值交换。这时xor操作的最经典的使用场景。例如：
基本操作
a=0^a=a^0
0=a^a
由上面两个推导出：a=a^b^b
交换两个数
a=a^b
b=a^b 实际上是原来的a^b^b
a=a^b 实际上是原来的a^b^a
移除最后一个 1
a=n&(n-1)
获取最后一个 1
diff=(n&(n-1))^n
136. 只出现一次的数字
难度简单1353
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (auto e: nums) ret ^= e;
return ret;
}
};剑指 Offer 56 - I. 数组中数字出现的次数 260. 只出现一次的数字 III
难度中等379
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]
leetcode官方解答
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int ret = 0;
for (int n : nums)
ret ^= n;
int div = 1;
while ((div & ret) == 0)
div <<= 1;
int a = 0, b = 0;
for (int n : nums)
if (div & n)
a ^= n;
else
b ^= n;
return vector<int>{a, b};
}
};剑指 Offer 56 - II. 数组中数字出现的次数 II 137. 只出现一次的数字 II
难度中等370
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (int i = 0; i < 32; ++i) {
int total = 0;
for (int num: nums) {
total += ((num >> i) & 1);
}
if (total % 3) {
ans |= (1 << i);
}
}
return ans;
}
};剑指 Offer 15. 二进制中1的个数 汉明重量 191. 位1的个数
难度简单177
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
n & (n - 1)可以消去n的二进制表示中最后一个1，所以经过多少次消去之后n变为0即n中有多少个1
class Solution {
public:
int hammingWeight(uint32_t n) {
int ret = 0;
while (n) {
n &= n - 1;
ret++;
}
return ret;
}
};461. 汉明距离 HOT100
难度简单400收藏分享切换为英文接收动态反馈
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
class Solution {
public:
int hammingDistance(int x, int y) {
int res = 0;
while(x | y){
if((x&1) ^ (y&1)){
res++;
}
x >>= 1;
y >>= 1;
}
return res;
}
};338. 比特位计数 HOT100
难度中等342
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]示例 2:
输入: 5
输出: [0,1,1,2,1,2]进阶:
- 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
- 要求算法的空间复杂度为O(n)。
//方法一：直接计算
class Solution {
public:
int countOnes(int x) {
int ones = 0;
while (x > 0) {
x &= (x - 1);
ones++;
}
return ones;
}
vector<int> countBits(int num) {
vector<int> bits(num + 1);
for (int i = 0; i <= num; i++) {
bits[i] = countOnes(i);
}
return bits;
}
};
//方法二：动态规划——最高有效位
class Solution {
public:
vector<int> countBits(int num) {
vector<int> bits(num + 1);
int highBit = 0;
for (int i = 1; i <= num; i++) {
if ((i & (i - 1)) == 0) {
highBit = i;
}
bits[i] = bits[i - highBit] + 1;
}
return bits;
}
};190. 颠倒二进制位
难度简单177
颠倒给定的 32 位无符号整数的二进制位。
示例 1：
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。示例 2：
输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。在这里，我们将展示基于上述逻辑的实现示例。
i n res
- 11001001 -
0 1100100 1
1 110010 10
2 11001 100
3 1100 1001
4 110 10010
5 11 100100
6 1 1001001
8 - 10010011
作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/reverse-bits/solution/fu-xue-ming-zhu-xun-huan-yu-fen-zhi-jie-hoakf/
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for (int i = 0; i < 32; ++i) {
res = (res << 1) | (n & 1);
n >>= 1;
}
return res;
}
};201. 数字范围按位与
难度中等130
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
示例 1:
输入: [5,7]
输出: 4示例 2:
输入: [0,1]
输出: 0官方解答
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int shift = 0;
// 找到公共前缀
while (m < n) {
m >>= 1;
n >>= 1;
++shift;
}
return m << shift;
}
};