Skip to content

Commit a383a04

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0461
No.0461.Hamming Distance
1 parent d20a267 commit a383a04

File tree

8 files changed

+84
-135
lines changed

8 files changed

+84
-135
lines changed

‎solution/0400-0499/0461.Hamming Distance/README.md

Lines changed: 34 additions & 53 deletions
Original file line numberDiff line numberDiff line change
@@ -43,12 +43,11 @@
4343

4444
<!-- 这里可写通用的实现逻辑 -->
4545

46-
利用异或运算的规律找出不同的位
46+
**方法一：位运算**
4747

48-
- 0 ^ 0 = 0
49-
- 1 ^ 1 = 0
50-
- 0 ^ 1 = 1
51-
- 1 ^ 0 = 1
48+
我们将 $x$ 和 $y$ 按位异或，得到的结果中的 $1$ 的个数就是汉明距离。
49+
50+
时间复杂度 $O(1)$，空间复杂度 $O(1)$。
5251

5352
<!-- tabs:start -->
5453

@@ -59,11 +58,7 @@
5958
```python
6059
class Solution:
6160
def hammingDistance(self, x: int, y: int) -> int:
62-
num, count = x ^ y, 0
63-
while num != 0:
64-
num &= num - 1
65-
count += 1
66-
return count
61+
return (x ^ y).bit_count()
6762
```
6863

6964
### **Java**
@@ -73,24 +68,27 @@ class Solution:
7368
```java
7469
class Solution {
7570
public int hammingDistance(int x, int y) {
76-
int num = x ^ y;
77-
int count = 0;
78-
while (num != 0) {
79-
num &= num - 1;
80-
count++;
81-
}
82-
return count;
71+
return Integer.bitCount(x ^ y);
8372
}
8473
}
8574
```
8675

87-
或者利用库函数 `Integer.bitCount()`
76+
### **C++**
8877

89-
```java
78+
```cpp
9079
class Solution {
91-
public int hammingDistance(int x, int y) {
92-
return Integer.bitCount(x ^ y);
80+
public:
81+
int hammingDistance(int x, int y) {
82+
return __builtin_popcount(x ^ y);
9383
}
84+
};
85+
```
86+
87+
### **Go**
88+
89+
```go
90+
func hammingDistance(x int, y int) int {
91+
return bits.OnesCount(uint(x ^ y))
9492
}
9593
```
9694

@@ -103,44 +101,27 @@ class Solution {
103101
* @return {number}
104102
*/
105103
var hammingDistance = function (x, y) {
106-
let distance = x ^ y;
107-
let count = 0;
108-
while (distance != 0) {
109-
count++;
110-
distance &= distance - 1;
104+
x ^= y;
105+
let ans = 0;
106+
while (x) {
107+
x -= x & -x;
108+
++ans;
111109
}
112-
return count;
110+
return ans;
113111
};
114112
```
115113

116-
### **C++**
114+
### **TypeScript**
117115

118-
```cpp
119-
class Solution {
120-
public:
121-
int hammingDistance(int x, int y) {
122-
x ^= y;
123-
int count = 0;
124-
while (x) {
125-
++count;
126-
x &= (x - 1);
127-
}
128-
return count;
116+
```ts
117+
function hammingDistance(x: number, y: number): number {
118+
x ^= y;
119+
let ans = 0;
120+
while (x) {
121+
x -= x & -x;
122+
++ans;
129123
}
130-
};
131-
```
132-
133-
### **Go**
134-
135-
```go
136-
func hammingDistance(x int, y int) int {
137-
x ^= y
138-
count := 0
139-
for x != 0 {
140-
count++
141-
x &= (x - 1)
142-
}
143-
return count
124+
return ans;
144125
}
145126
```
146127

‎solution/0400-0499/0461.Hamming Distance/README_EN.md

Lines changed: 30 additions & 48 deletions
Original file line numberDiff line numberDiff line change
@@ -51,36 +51,35 @@ Use xor operation to find different bits.
5151
```python
5252
class Solution:
5353
def hammingDistance(self, x: int, y: int) -> int:
54-
num, count = x ^ y, 0
55-
while num != 0:
56-
num &= num - 1
57-
count += 1
58-
return count
54+
return (x ^ y).bit_count()
5955
```
6056

6157
### **Java**
6258

6359
```java
6460
class Solution {
6561
public int hammingDistance(int x, int y) {
66-
int num = x ^ y;
67-
int count = 0;
68-
while (num != 0) {
69-
num &= num - 1;
70-
count++;
71-
}
72-
return count;
62+
return Integer.bitCount(x ^ y);
7363
}
7464
}
7565
```
7666

77-
Or use the library function `Integer.bitCount()`
67+
### **C++**
7868

79-
```java
69+
```cpp
8070
class Solution {
81-
public int hammingDistance(int x, int y) {
82-
return Integer.bitCount(x ^ y);
71+
public:
72+
int hammingDistance(int x, int y) {
73+
return __builtin_popcount(x ^ y);
8374
}
75+
};
76+
```
77+
78+
### **Go**
79+
80+
```go
81+
func hammingDistance(x int, y int) int {
82+
return bits.OnesCount(uint(x ^ y))
8483
}
8584
```
8685

@@ -93,44 +92,27 @@ class Solution {
9392
* @return {number}
9493
*/
9594
var hammingDistance = function (x, y) {
96-
let distance = x ^ y;
97-
let count = 0;
98-
while (distance != 0) {
99-
count++;
100-
distance &= distance - 1;
95+
x ^= y;
96+
let ans = 0;
97+
while (x) {
98+
x -= x & -x;
99+
++ans;
101100
}
102-
return count;
101+
return ans;
103102
};
104103
```
105104

106-
### **C++**
105+
### **TypeScript**
107106

108-
```cpp
109-
class Solution {
110-
public:
111-
int hammingDistance(int x, int y) {
112-
x ^= y;
113-
int count = 0;
114-
while (x) {
115-
++count;
116-
x &= (x - 1);
117-
}
118-
return count;
107+
```ts
108+
function hammingDistance(x: number, y: number): number {
109+
x ^= y;
110+
let ans = 0;
111+
while (x) {
112+
x -= x & -x;
113+
++ans;
119114
}
120-
};
121-
```
122-
123-
### **Go**
124-
125-
```go
126-
func hammingDistance(x int, y int) int {
127-
x ^= y
128-
count := 0
129-
for x != 0 {
130-
count++
131-
x &= (x - 1)
132-
}
133-
return count
115+
return ans;
134116
}
135117
```
136118

‎solution/0400-0499/0461.Hamming Distance/Solution.cpp

Lines changed: 1 addition & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,6 @@
11
class Solution {
22
public:
33
int hammingDistance(int x, int y) {
4-
x ^= y;
5-
int count = 0;
6-
while (x) {
7-
++count;
8-
x &= (x - 1);
9-
}
10-
return count;
4+
return __builtin_popcount(x ^ y);
115
}
126
};

‎solution/0400-0499/0461.Hamming Distance/Solution.go

Lines changed: 1 addition & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,3 @@
11
func hammingDistance(x int, y int) int {
2-
x ^= y
3-
count := 0
4-
for x != 0 {
5-
count++
6-
x &= (x - 1)
7-
}
8-
return count
2+
return bits.OnesCount(uint(x ^ y))
93
}

‎solution/0400-0499/0461.Hamming Distance/Solution.java

Lines changed: 2 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,5 @@
11
class Solution {
22
public int hammingDistance(int x, int y) {
3-
// return Integer.bitCount(x ^ y);
4-
int num = x ^ y;
5-
int count = 0;
6-
while (num != 0) {
7-
num &= num - 1;
8-
count++;
9-
}
10-
return count;
3+
return Integer.bitCount(x ^ y);
114
}
12-
}
5+
}

‎solution/0400-0499/0461.Hamming Distance/Solution.js

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -4,11 +4,11 @@
44
* @return {number}
55
*/
66
var hammingDistance = function (x, y) {
7-
let distance = x ^ y;
8-
let count = 0;
9-
while (distance != 0) {
10-
count++;
11-
distance &= distance - 1;
7+
x ^= y;
8+
let ans = 0;
9+
while (x) {
10+
x -= x & -x;
11+
++ans;
1212
}
13-
return count;
13+
return ans;
1414
};

‎solution/0400-0499/0461.Hamming Distance/Solution.py

Lines changed: 1 addition & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,3 @@
11
class Solution:
22
def hammingDistance(self, x: int, y: int) -> int:
3-
num, count = x ^ y, 0
4-
while num != 0:
5-
num &= num - 1
6-
count += 1
7-
return count
3+
return (x ^ y).bit_count()

‎solution/0400-0499/0461.Hamming Distance/Solution.ts

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
function hammingDistance(x: number, y: number): number {
2+
x ^= y;
3+
let ans = 0;
4+
while (x) {
5+
x -= x & -x;
6+
++ans;
7+
}
8+
return ans;
9+
}

0 commit comments

Comments
 (0)