ADM-201 dump PMP dumps pdf SSCP exam materials CBAP exam sample questions

算法:位运算 – 译学馆
未登录,请登录后再发表信息
最新评论 (0)
播放视频

算法:位运算

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.
像583这样的数有何意义?
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.
现在来讲讲加法
Now let’s talk about adding.
十进制中两个数字相加
Well in base-10 we add up the two digits
达到数位限制就要向前一位进位
and if it hits our limit then we roll that over
所以 3加7得10
to the next digit so we added 3 and the
达到限制10 就向前一位进1
7, that gets ten, that hits our limit of ten, so we roll that one over and now we’re
把1 8 3相加 结果是12
adding a 1, an 8, and a 3,and that
向前一位进1 个位留下2
gives us 12 so we got a two down here that hits
然后把6 5 1相加
our limit of 10 so we roll that over up here, and then we’re adding a 6, a 5 and
它同样达到了限制 所以留下2
a 1, and that again hits our limit of 10 per digit, so we go down that
进位1 结果是1220
two and we carry the 1 over and we get 1220.
在二进制里同样可以这样做
So we can do that exact same thing
在二进制里 每个数位的限制为2
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
所以在这里记一个0 进位1
record a 0 over here, carry the one,
现在再加上1 0 1 会再次达到限制
now we’re going to add again a 1, a 0, and a 1. That’s going again hit our limit of
在这记一个0 进位1 现在1和1相加
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.
再次达到限制 就在这记一个0 进位1
Again we’re hitting this limit of two so we’re going to record a 0 here and carry
结果是1000 这就是二进制加法
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,
第2位元到第8位元上的数
to the positive version, to the absolute value to get to the 8th in this case.
我们用8是因为它是8位的数
We use 8 because it’s an 8-bit number. So let’s think
想想0010010加上什么数
about this. What number would we have to add to 0010010
会得到10000000
to get 1 000 000 0. Well if we
若把0010010取反再加上它本身
just added the inverse of 0 0 100 10 to
结果就是0加上后面一连串的1
it then we would get 0 with a whole bunchof ones afterwards.
因而如果在这里加上1 在下面加上1
Therefore if we add 1 up here and a 1
就能得到所要的值
down here we should get the values we’re looking for.
记得原问题是如何用二进制表示-18
So remember that our original question was how do we represent negative 18 in binary?
取它的正值18 看一下二进制表示
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
再加1 得到1101110
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.
这就是二进制里表示-18的方法
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.
若要把-123转换成二进制
So if we want to convert negative 123 to binary
需要找与123无符号位相加的数
we’d be looking for the thing that we add to 123’s non sign bits,
即这里的第2到第8位元
so these bits over here, to get to the 8th.
把123转换成二进制
So we’d take 123, convert it to binary, so we get
然后取反再加上1
that then invert all of the bits, and then we add 1 to that.
就会得到-123的补码
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.
有趣的是 最上面的数是23
Interestingly that top number is 23
左移后的数是46 右移后的数是11
and this left shift number is 46 and the right shift number is 11.
你在这些数里发现了什么
Now what do you notice about those numbers?
左移后的数相当于原数乘2
Well the left shift had the effect of multiplying that number by 2
右移效果和除以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.
考虑数字-23的逻辑移位
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.
结果是一个奇怪的值116
This gets us this weird value of 116 which doesn’t really seem to have any
它看起来和-23没啥关系
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
而不是像逻辑右移位那样填充0
with a 0 as in the logical right shift.
结果是-12
The resulting number is negative 12 which
它依然保持那一种除以2的关系
does still bear that sort of, that divide by 2 relationship,
除了-23除以2是-11.5外
except that with negative 23 dividing by 2 is negative 11.5
所以这样就只是约等于-12
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
只有两位元都为1 相与的结果才是1
and two bits we get a 1 only if both of those bits are 1.
两位元至少有一个为1 相或结果就为1
When we or two bits we get a 1 if either of those two bits are 1.
两位元有且只有1个为1 异或结果为1
And when we do an XOR we need exactly one of those two bits to be a 1.
如果两位元都为1 异或结果为0
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
若这个位元是1或0时该怎样做?
if say this bit was a one or a zero?
若我们创建一个掩码
Well if we create a mask or just a number
或一个只有一个位元为1的数
that has a 1 only in that one bit
把它和原来的数相与
and we and it with the original number that will indicate
可以知道原值是1或0
whether that value is a one or a zero
因为只要有一个是0 结果就是0
because if there’s a zero there the whole number will be 0.
否则结果就比0大
Otherwise it’ll be something bigger than 0,
所以将1向左移i位就能创建这个掩码
so that mask can be created by taking one and shifting it over to the left by i spots.
为了求出第i点是1或0 只需比较X
So to figure out if the ith spot is a one or a zero we just compare X,
将X和那个掩码相与 看看是否等于0
do an and of X with that mask and say does that not equal 0?
那现在第i个位的设置呢?做法非常相似
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.
就能保证第i个位的设置
And that will make sure that ith bit is set.
那如何清除第i个位元呢
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
其它位全是1的掩码相与
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

审核员

审核团O

视频来源

https://www.youtube.com/watch?v=NLKQEOgBAnw

相关推荐