• #### 科普

SCIENCE

#### 英语

ENGLISH

#### 科技

TECHNOLOGY

MOVIE

FOOD

#### 励志

INSPIRATIONS

#### 社会

SOCIETY

TRAVEL

#### 动物

ANIMALS

KIDS

#### 卡通

CARTOON

#### 计算机

COMPUTER

#### 心理

PSYCHOLOGY

#### 教育

EDUCATION

#### 手工

HANDCRAFTS

#### 趣闻

MYSTERIES

CAREER

GEEKS

#### 时尚

FASHION

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

点击下载Android最新版本

点击下载iOS最新版本 扫码下载译学馆APP

#### 算法：位运算

Algorithms: Bit Manipulation

Hi, I’m Gayle Laakmann McDowell,
《程序员面试金典》作者
author of Cracking the Coding Interview.

Today we’re going to talk about bits.

So we’re going to talk about how positive and negative numbers are represented in binary.

We’re going to talk about operations like shifting and arithmetic

including the logical and the arithmetic shift.

And then I’m going to talk about how we can use masks

to do operations like clearing, setting, and getting bits.

Now there’s a little bit of cross dependency in these topics

so the order might seem a little bit funny to be jumping back and forth,

but it’ll be a little better this way.

So let’s relate this to base 10 numbers.

What does a number like 583 mean?

What do those digits represent? Well
5×10²+8×10¹+3×10⁰
it’s five times ten to the second, plus 8 times 10 to the first, plus 3 times 10 to

the 0th. In base 2 or binary we can do the exact same thing.

Well in base-10 we add up the two digits

and if it hits our limit then we roll that over

to the next digit so we added 3 and the

7, that gets ten, that hits our limit of ten, so we roll that one over and now we’re

adding a 1, an 8, and a 3,and that

gives us 12 so we got a two down here that hits

our limit of 10 so we roll that over up here, and then we’re adding a 6, a 5 and

a 1, and that again hits our limit of 10 per digit, so we go down that

two and we carry the 1 over and we get 1220.

So we can do that exact same thing

in binary. In binary of course our limit of each digit is just 2, so we’re going to
1和1相加 结果将会达到限制2
add this 1 and this 1, and that’s going to hit our limit of two so we’re going to

record a 0 over here, carry the one,

now we’re going to add again a 1, a 0, and a 1. That’s going again hit our limit of

2 so I’m going to record a 0 there, carry the 1 over and now we’re going to add a 1 and a 1.

Again we’re hitting this limit of two so we’re going to record a 0 here and carry

the 1 over and we get 1000. So that’s again how you do binary addition.

It’s very very parallel to what you do in base-10.

Now let’s talk about how we represent negative numbers on a computer.

Typically a negative integer is stored in two’s complement form and what

this means is that the very first bit is used to represent this sign. A 0 means it’s
0表示正数 1表示负数
it’s a positive number and a one means it’s negative.

Then the remaining bits over here

are filled in with the two’s complement,

the number that you’d have to add to these,

to the positive version, to the absolute value to get to the 8th in this case.

We use 8 because it’s an 8-bit number. So let’s think

to get 1 000 000 0. Well if we

just added the inverse of 0 0 100 10 to

it then we would get 0 with a whole bunchof ones afterwards.

Therefore if we add 1 up here and a 1

down here we should get the values we’re looking for.

So remember that our original question was how do we represent negative 18 in binary?

Well we take the positive value of that, the 18 and we look at this binary

representation and then we say what number can we add to that to get one
1后面加上一连串的0？
followed by whole bunch of zeros?

Well the number we add to it to get all one’s is just invert all the numbers so

if we add 1 to a bunch of the, to both of those, then we have 110 1110

so therefore you add to the two’s complement,

the number that you add to this series of bits here

is in fact that number

so our representation is this right here.

So that’s how you represent negative 18 in binary. So just to make sure you

understand that. Let’s look at one more example.

So if we want to convert negative 123 to binary

we’d be looking for the thing that we add to 123’s non sign bits,

so these bits over here, to get to the 8th.

So we’d take 123, convert it to binary, so we get

that then invert all of the bits, and then we add 1 to that.

And that will give us our two’s complement version of negative 123. The

next topic I want to talk about is shifting. Specifically two types of shifting,

logical shifting and arithmetic shifting.

So let’s consider some number in binary like this.

So if we want to left shift then we just move everything

over by one to the left and if we want to right shift, move everything over by one to the right.

Now we’ve been talking about these in binary so much

we forgot what these numbers actually are in base-10.

Interestingly that top number is 23

and this left shift number is 46 and the right shift number is 11.

Now what do you notice about those numbers?

Well the left shift had the effect of multiplying that number by 2

and the right shift had the effect of dividing it by two.

Of course with some truncation in there, and that’s not a coincidence.

That’s what a left shift a right shift generally do.

Now some of you might be wondering

what happens on a negative number to this sign bit if we’re doing a right shift?

Does it shift with the number or not?

And that’s an interesting question.

And that’s where you get into logical vs arithmetic right shifts.

So let’s consider the number negative 23.

In a logical right shift we do what we would logically think that a right shift would do,

we move everything including the sign bit over.

This gets us this weird value of 116 which doesn’t really seem to have any

particular relationship to the number negative 23.

The arithmetic right shift operates slightly differently

but in doing so preserves an arithmetic relationship between

the original number and the new right shifted number.

What the arithmetic right shift does is it shifts everything over by one including the sign bit

but then it fills in the sign bit with the original sign bit instead of

with a 0 as in the logical right shift.

The resulting number is negative 12 which

does still bear that sort of, that divide by 2 relationship,

except that with negative 23 dividing by 2 is negative 11.5

so we’re rounding to negative 12 this time.

So now we’re on to our final topic – using masks to do things

like getting a bit, updating it, things like that.

First let’s review some of the basics. When we

and two bits we get a 1 only if both of those bits are 1.

When we or two bits we get a 1 if either of those two bits are 1.

And when we do an XOR we need exactly one of those two bits to be a 1.

If both are ones we get a zero. So now let’s

turn to how you would get a particular bit and a number. So how do we figure out

if say this bit was a one or a zero?

Well if we create a mask or just a number

that has a 1 only in that one bit

and we and it with the original number that will indicate

whether that value is a one or a zero

because if there’s a zero there the whole number will be 0.

Otherwise it’ll be something bigger than 0,

so that mask can be created by taking one and shifting it over to the left by i spots.

So to figure out if the ith spot is a one or a zero we just compare X,

do an and of X with that mask and say does that not equal 0?

Now what about setting the ith bit? Well we can do a very similar thing.

We create actually exact, the exact same mask and

we just or it with that original value.

And that will make sure that ith bit is set.

Now what about clearing the ith bit?

Well that’s a little bit trickier but still very doable.

What we want to do is and it with a mask that has

a 1 everywhere else but that

one spot. But how do we create such a mask?

Well all we have to do actually is just take the mask from before and invert it and

that’s exactly what you see here.

So we’ve now covered the basics of bit manipulation.

We talked about how numbers are represented both in positive and negative form,

and then we talked about different operations like,

how we add numbers comparing that to base 10 numbers.

We talked about shifting both logical and arithmetic

and then we talked about how to do getting, setting, and clearing using masks.

So from candidates there’s a lot of focus on

learning different bit manipulation tricks and things like that.

What I really encourage people to do is just

really solidify their understanding of the basics

and from there a lot of these tricks and things like that will follow,

but really nail that foundation of the basics.

So now that you’ve seen these basic operations

why don’t you try your hand at a new bit manipulation problem.

Good luck.

B11101001