算法与数据结构学习笔记:二进制

本文最后更新于:November 28, 2021 am

常见二进制操作

C++位运算符

下表显示了 C++ 支持的位运算符。

假设如果 A = 60,且 B = 13,现在以二进制格式表示,它们如下所示:

A = 0011 1100

B = 0000 1101

则:

运算符描述实例
&如果同时存在于两个操作数中,二进制 AND 运算符复制一位到结果中。(A & B) 将得到 12,即为 0000 1100
|如果存在于任一操作数中,二进制 OR 运算符复制一位到结果中。(A | B) 将得到 61,即为 0011 1101
^如果存在于其中一个操作数中但不同时存在于两个操作数中,二进制异或运算符复制一位到结果中。(A ^ B) 将得到 49,即为 0011 0001
~二进制补码运算符是一元运算符,具有”翻转”位效果,即0变成1,1变成0。(~A ) 将得到 -61,即为 1100 0011,一个有符号二进制数的补码形式。
<<二进制左移运算符。左操作数的值向左移动右操作数指定的位数。A << 2 将得到 240,即为 1111 0000
>>二进制右移运算符。左操作数的值向右移动右操作数指定的位数。A >> 2 将得到 15,即为 0000 1111

基本操作

a=0^a=a^0

0=a^a

由上面两个推导出:a=a^b^b

交换两个数

a=a^b

b=a^b

a=a^b

移除最后一个 1

a=n&(n-1)

获取最后一个 1

diff=(n&(n-1))^n

常见题目

136. 只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

image-20200807111500764

image-20200807111619453

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret=0;
for(auto num:nums)
{
ret^=num;
}
return ret;

}
};

137. 只出现一次的数字 II

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

1
2
输入: [2,2,3,2]
输出: 3

示例 2:

1
2
输入: [0,1,0,1,0,1,99]
输出: 99
遍历统计

如果所有数字都出现了 3 次,那么每一列的 1 的个数就一定是 3 的倍数。之所以有的列不是 3 的倍数,就是因为只出现了 1 次的数贡献出了 1。所以所有不是 3 的倍数的列写 1,其他列写 0 ,就找到了这个出现 1 次的数。

假如例子是 1 2 6 1 1 2 2 3 3 3, 3 个 1, 3 个 2, 3 个 3,1 个 6
1 0 0 1
2 0 1 0
6 1 1 0
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1
3 0 1 1
3 0 1 1
看最右边的一列 1001100111 有 6 个 1
再往前看一列 0110011111 有 7 个 1
再往前看一列 0010000 有 1 个 1
我们只需要把是 3 的倍数的对应列写 0,不是 3 的倍数的对应列写 1
也就是 1 1 0,也就是 6。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret=0;
for(int i=0;i<32;i++)
{
int sum=0;
for(int j=0;j<nums.size();j++)
{
sum+=(nums[j]>>i)&1;

}
ret^=(sum%3)<<i;

}
return ret;

}
};
有限状态自动机