• #### 科普

SCIENCE

#### 英语

ENGLISH

#### 科技

TECHNOLOGY

MOVIE

FOOD

#### 励志

INSPIRATIONS

#### 社会

SOCIETY

TRAVEL

#### 动物

ANIMALS

KIDS

#### 卡通

CARTOON

#### 计算机

COMPUTER

#### 心理

PSYCHOLOGY

#### 教育

EDUCATION

#### 手工

HANDCRAFTS

#### 趣闻

MYSTERIES

CAREER

GEEKS

#### 时尚

FASHION

• 精品课
• 公开课
• 欢迎下载我们在各应用市场备受好评的APP

点击下载Android最新版本

点击下载iOS最新版本

扫码下载译学馆APP

#### 算法：用位运算解决孤单整数的问题

Algorithms: Solve 'Lonley Integer' Using Bit Manipulation

Hi, I’m Gayle Laakmann McDowell, author of Cracking the Coding Interview.

Today I’m going to cover the lonely integer problem.

So suppose we have an array of integers and all the numbers appear twice

except for one number that only appears once.

So how do we find that number, the lonely integer?

Well one way is using a hashmap. So we can store all the

elements in a hashmap and count how many times each character appears, or each

integer appears, and if something only appears once then that is of course the lonely

integer. But how can we reduce the space complexity even further? We can’t reduce

the time complexity because well we have to touch every element anyway. So how can

we reduce the space complexity?

Well let’s think about these numbers in binary.

The reason why binary is a good

bet here is that if we want to reduce the space complexity

we’re probably talking about constant space and

that means we can’t keep really any data

structures we don’t have that much else to work with other than some sort of

crazy bit issue. So let’s think about the bits here. Consider just that last bit

there. If every number appeared twice, and literally every single number, then we’d
1的个数就为偶数 若1的个数不是偶数
see an even number of ones. If we don’t see an even number of ones then

that means that there’s a one in that bit for the lonely integer.

So we could go through and actually count the number of ones.

Another thing we could do is just XOR everything, because if there’s an even

number of ones, we’ll wind up with a zero, which means that the lonely integer has

a zero but if there’s an odd number of ones, we’ll wind up with a 1. So XORing all of those in

Well if we explore all of these again we’re going to get a 1

and if we XOR all of these here we’re going to get a 0 because have an even number of ones and
1异或1得0 接着再将这些数相异或
1 XOR with 1 is 0. And if we XOR all of these, again,

if we have an even number of ones, we have two 1s,

so we’re going to get a 0 here.

So what we can do actually, rather than walking

through this bit by bit by bit, we can walk through our whole list, XOR all the

values and interestingly that resulting

value will be the lonely integer. So implementing this is now almost trivial. We

just have some result which starts off at zero, walk through each value in my

array, and XOR everything together.

And then just return my result. So bit

manipulation problems are often, are one of those problems that do kind of

involve aha moments sometimes, so one tip off is if you’re asked to keep the

time complexity really really fast but still reduce the space complexity even

more, especially like for constant time, that sometimes where you’re going to want

some bit manipulation approach. The other tip is when you are tackling a

bit manipulation problem, try looking at it bit by bit rather than with all

the integers at once, and explore what the result of different operations like

anding and XORing and shifting would give you. So keep those things in mind

and you know, practice bit manipulation problems. They aren’t necessarily that hard once

you get a hang of them, once you get over the like intimidation factor.

Good luck.

B11101001