algorithm-pattern-cpp/data_structure/binary_op.md at master · da183/algorithm-pattern-cpp · GitHub

History

213 lines (171 loc) · 5.73 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

# 二进制

## 常见二进制操作

### 基本操作

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

## 常见题目

[single-number](https://leetcode-cn.com/problems/single-number/)

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

```c++

int singleNumber(vector<int>& nums) {

// 10 ^10 == 00

// 两个数异或就变成0

auto result = 0;

for (const auto &num : nums) {

result ^= num;

}

return result;

}

```

[single-number-ii](https://leetcode-cn.com/problems/single-number-ii/)

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

```c++

// 思路：每一位，统计有多少个1，除以3取余数

// 出现三次的，取余数为0，被过滤掉，剩下的都是只出现一次的那个数

int singleNumber(vector<int>& nums) {

auto ret = 0;

for (int i = 0; i < 32; ++i) {

auto sumOne = 0;

for (const auto &item : nums) {

sumOne += (item >> i) & 1;

}

ret ^= (sumOne % 3) << i;

}

return ret;

}

```

[single-number-iii](https://leetcode-cn.com/problems/single-number-iii/)

> 给定一个整数数组 `nums`，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

```c++

vector<int> singleNumber(vector<int>& nums) {

auto diff = 0;

// 按位与，出现两次的数会被剔除掉

for (const auto &item : nums) {

diff ^= item;

}

vector<int> result(2);

// 只出现一次的两个数不想等，则其异或的结果必然至少有一位为 1

// 找到最后一个 '1'

diff &= (-diff);

// 再按该位上的值为1还是为0将所有的数分成两组进行异或把两个数分开

for (const auto &num : nums) {

if ((diff & num) == 0) {

result[0] ^= num;

} else {

result[1] ^= num;

}

return result;

}

```

> 关于 x & (-x)

> 在计算机系统中，数值一律用补码来表示和存储

> 一个正数 x 与其相反数 -x，只有一位同时为 '1'，并且总为 x 中的最后一位 '1'

> 正数的补码与原码相同

> 负数的补码，将其原码除符号位外的所有位取反后加1

> 10和-10用8位表示为：

> 10: 0000 1010

> -10: 1111 1010

> 因此，x & (-x) 可用于求出x中最后一个'1'

[number-of-1-bits](https://leetcode-cn.com/problems/number-of-1-bits/)

> 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为[汉明重量](https://baike.baidu.com/item/%E6%B1%89%E6%98%8E%E9%87%8D%E9%87%8F)）。

```c++

int hammingWeight(int n) {

auto ret = 0;

while (n != 0) {

n = n & (n - 1);

++ret;

}

return ret;

}

```

[counting-bits](https://leetcode-cn.com/problems/counting-bits/)

> 给定一个非负整数 **num**。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

```c++

vector<int> countBits(int num) {

vector<int> ret(num+1);

for (int i = 0; i <= num; ++i) {

ret[i] = hammingWeight(i);

}

return ret;

}

int hammingWeight(int n) {

auto ret = 0;

while (n != 0) {

n = n & (n - 1);

++ret;

}

return ret;

}

```

另外一种动态规划解法

```c++

vector<int> countBits(int num) {

vector<int> ret(num + 1);

for (int i = 1; i <= num; ++i) {

// 对于 i，其二进制1的个数 = 移除其最后一个1剩余的1的个数 + 1

// i & (i - 1)移除最后一个1

ret[i] = ret[i & (i - 1)] + 1;

}

return ret;

}

```

[reverse-bits](https://leetcode-cn.com/problems/reverse-bits/)

> 颠倒给定的 32 位无符号整数的二进制位。

思路：依次颠倒即可

```c++

uint32_t reverseBits(uint32_t n) {

uint32_t ret = 0; // 记得初始化，否则通不过

auto pow = 31;

while(n != 0) {

// 取最后一位进行左移

ret += (n & 1) << pow;

n >>= 1;

--pow;

}

return ret;

}

```

[bitwise-and-of-numbers-range](https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/)

> 给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

```c++

* 思路：

* 只要有一位不同时位1，则按位与结果为0

* 因此，从m和n最左边一个不同时为1的位起，其右边的位都将被剔除，如：

* m = 5 0101

* n = 15 1111

* 后面2位最终会变为0

* 所以，掐头去尾取中间（左边起第二个1）么？

* 不，n再大也没用，m跟n最左边的1必须在同一位，否则结果直接为0

* 毕竟终归是会有一个中间的数，10000，按位与完，m就没了

* 所以，m、n同时右移，直到二者相等（剩下最左边的若干个1，或者为0）

* 再进行左移

int rangeBitwiseAnd(int m, int n) {

auto zeroNum = 0;

while (m != n) {

m >>= 1;

n >>= 1;

++zeroNum;

}

return m << zeroNum;

}

```

## 练习

- [ ] [single-number](https://leetcode-cn.com/problems/single-number/)

- [ ] [single-number-ii](https://leetcode-cn.com/problems/single-number-ii/)

- [ ] [single-number-iii](https://leetcode-cn.com/problems/single-number-iii/)

- [ ] [number-of-1-bits](https://leetcode-cn.com/problems/number-of-1-bits/)

- [ ] [counting-bits](https://leetcode-cn.com/problems/counting-bits/)

- [ ] [reverse-bits](https://leetcode-cn.com/problems/reverse-bits/)

algorithm-pattern-cpp/data_structure/binary_op.md at master · da183/algorithm-pattern-cpp · GitHub

Expand file tree

Breadcrumbs

binary_op.md

Latest commit

History

Breadcrumbs

binary_op.md

File metadata and controls