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

二进制到BCD编码(double dabble算法) – 译学馆
未登录,请登录后再发表信息
最新评论 (0)
播放视频

二进制到BCD编码(double dabble算法)

Binary to BCD (Double Dabble Algorithm) - Computerphile

In some ways there are some awkward incompatibilities
我们平时喜欢使用的十进制
between the decimal that we like to use and the binary,
和对计算机来说更为高效的二进制之间
which is so efficient and wonderful for computers to use.
在某些方面上的兼容性有些尴尬
We’ve seen one example of this already.
我们已经看过一个这样的例子
I think I’ve mentioned it in a previous video
我想我在以前的一个视频中提到过
that 0.1, or 0.10, ten cents in other words, in decimal
十进制中的0.1或0.10
in your current bank balance
也就是银行账户中的10美分
is not exactly representable as a binary number.
不能用一个二进制数字精确地表达出来
You look at what it is in binary
看看它在二进制中是什么
0.000110011…
0.000110011……
It just isn’t, you know. It keeps on recurring.
它并不是精确的 它一直在循环
Just as 1/3 in decimal isn’t exact,
就像1/3在十进制中不能精确表达
it goes 0.333333… forever.
它是0.3333333……一直循环

<电脑狂热>
Decimal and binary sometimes don’t mix.
十进制和二进制有时候不能混为一谈
Now here’s going to be a classic example.
现在来看一个经典的例子
Let’s just think this through, without even writing anything down.
我们可以只用脑袋想 甚至都不用写下来
If we’ve got a 4-bit nibble,
假设我们有一个4比特的半字节
we know that in hex it goes from 0000 to 1111,
我们知道十六进制的范围是从0000到1111
15 represented as f.
f代表15
Can’t use that full range.
但这个范围并非全部可用
This is binary-coded decimal,
因为这是二进制编码的十进制数
not binary-coded hexadecimal. Yeah?
不是二进制编码的十六进制数 对吧?
We have got to say,
你必须明白
the moment that representation, even in one nibble,
即使是在半字节中 只要数字
gets to 1010, that is 10.
变成了1010 那就是十进制的10
You can’t leave it as 1010.
你不能把1010放着不管了
You’ve now got to have 2 nibbles:
现在 我们来看两个半字节
the left nibble with a 1 in it
左边的半字节里是1
and the right nibble wants to look like 0.
右边的半字节里是0
You can’t compress it into a single nibble,
你不能把它压缩在一个单独的半字节中
say “1010”
说它是1010
I’m sorry folks, you’ll have to learn hex,
我很抱歉 朋友们 你们必须学习十六进制
because otherwise you won’t understand your bank balance.
否则你就看不懂你的账户余额
This is not going to go down very well.
这样可不好
The challenge then is, if you’re using a 4-bit nibble,
问题来了 如果你要用一个4比特的半字节
but only for the decimal range 0 to 9,
来表示十进制里的0~9
you’ve somehow got to make, in all your bit twiddles,
你必须注意 在所有的位运算中
you’ve got to make it carry into another nibble
要保证在数字变成10的时候
on the left at 10,
在其左侧插入另一个半字节
and not at 16,
而不是在16的时候
which is what hexadecimal will do for you.
那是十六进制运算会做的
So how does one, sort of, bridge that gap?
那么应该如何消除两者之间的差异?
Probably the best way for me to
在我看来 解决这个难点的
get in to the hard bit about this
最好方式
is go straight away for that magic number 10.
是直接来看一个神奇的数字10
Let’s represent it in binary
我们用二进制来表示它
and then say: How do we convert it into BCD?
然后想想:如何把它转换成BCD码?
and realize that we need that second nibble on the left.
然后你会意识到 我们需要在左边插入第二个半字节
What I’d like to do here is to draw myself columns,
现在我会画几个列
and I’m going to restrict myself to things that are, at most, 2 decimal digits.
然后将其限制在至多两位十进制数
Let’s remind ourselves, up here,
我们来回想一下 在这里
that we’re going to have a tens nibble
我们需要一个十位数的半字节
and a units nibble,
和一个个位数的半字节
and we’ll initialize everything to zeros.
将它们的初始值都设为0
But, above here, just to keep things very simple,
但是 这里为了简化
we’ll use 4-bit binary representations.
我们使用4位二进制表示法
And I hope you will all agree that
我希望你们都能接受
1010 is ten in base ten.
1010是二进制里的10
And the reason for that is that the binary in 4 bits
由于我们用了4比特的二进制
that’s an 8, that’s a 2, so that’s 10.
这是8 这是2 加起来就是10
This technique which is called Double Dabble
这就是Double Dabble算法
I don’t know how it was discovered,
我不知道它是怎么被发明的
it’s fiendishly clever.
这太聪明了
But the idea is, we’d love to convert binary into BCD
它的原理是 我们要把二进制转变为BCD码
by as far as possible
尽可能地只使用
using simple bit shifts all the time,
一些简单的位的移动
and doing the minimum of mucking about,
同时尽可能地减少操作
to get it to carry early.
尽快得到正确结果
So the “Double” reflects the fact
所以“Double”指的是
that we’re gonna shift this bit-pattern across into here.
我们要把位组合移动到这里
And we’re going to regard it as one huge, great, big, 12-bit register here.
我们将把它视为一个巨大的十二位的寄存器
A walloping, great shift register, all joined together.
这个巨大的移位寄存器组合在一起
Even though I’ve drawn it out separately,
虽然我将它分离出来
it’s just gonna move from the right across to the left, and move them across.
但它会从右边移动到左边 都移过来
And remember, every time you shift the thing by one place left
别忘了 每次你向左移动一位
you are basically doubling it.
它实际上是加倍了
Ok, that’s where the “Double” comes from.
这就是“Double”的由来
But we find we have to intervene to make it look right at the end,
但我们必须采取干预措施 以得到正确结果
and that is where the “Dabble” comes from.
这就是“Dabble”的由来
If you look up “dabble”, as I did in the Chambers Dictionary,
如果你像我一样在《钱伯斯词典》中查过dabble
one of the meanings is, ‘”to make trivial alteration to”
它的其中一个含义是“对某事做一些不重要的改变”
OK. To make a small alteration to something,
当你对一些东西做小小的修改
you’re “dabbling” with it.
就是在“dabble”它
OK, so that’s where Double Dabble comes.
这就是Double Dabble名称的由来
Ok, so it’s basically doubling,
这基本上就是把数字加倍
with a little bit of dabbling.
再做一点点微调
And the truth really hits you at 10.
看看十进制的10 你就明白了
So let’s progressively shift this by 1 bit left.
我们把这些数字依次向左移动1位
What’s gonna happen first of all?
首先会发生什么呢?
You shift over that 1 bit.
你移动了一位
You push it across into here
你把它移动到这里
because this is a unified register for the moment.
因为此时这个寄存器是一个整体
Purists what would say: “Ah! But when you shift left, like that,
纯粹主义者可能会说:当你像这样向左移动时
you should fill in with zeros on the right.”
你应该用0填满右边的空白处”
Yes, that is what will actually happen, inside the hardware,
是的 在计算机硬件中这确实会发生
But I prefer not to pad with zeros on the right as I shift,
但我不想在移动时用0填满右边的空格
because I want you to see when I’ve finished.
因为我希望你能看到最终的结果
So we could call this shift No.1.
我将其称它为第一次移动
Let’s do another one.
让我们来做下一个
That one moves into that position,
这次移动到了这里
but you’re bringing over another 0 out of that part,
但是你要把另外一个0从那一部分移过来
and that’s leaving you with 10 in there.
那里会剩下1 0
Now notice what’s happened.
现在看看 发生了什么
On shift 1 here,
在第一次移动后
you had a 1 of the right, in that nibble.
在你右边的半字节中会有一个1
By the time you’ve shifted it left one place,
当你将它向左移一格
it’s in the 2’s position.
它就在十进制2的位置上
So you’ve doubled it. Let’s do shift 3.
所以说它加倍了 我们来做第三次移动
And a zero is left,
这时还剩一个0
so, that is shift 3.
这就是第三次移动
Now, this is where we can begin to see trouble on the horizon.
现在我们就开始能看出问题了
We have got one more shift left to do,
我们还要再向左移一格
and if you don’t do anything about it,
如果你不对它进行任何操作
it’s just gonna end up with 1010 in here.
它将以1010结束
I mean, all right, what’s happened here, look,
我的意思是 看这里发生了什么
is that was two. You doubled it.
那本来是2 你把它加倍了
But because you shifted a 1 in and not a 0, you’ve doubled it and added 1.
但因为你移动的是1而不是0 它在加倍后又加了1
That now says 5, OK?
现在这是十进制中的5 对吗?
So basically it’s doubling.
所以基本上 它是加倍了
But sometimes if the bit you shift over is 1
但如果你移动的数字是1
and not a 0, it’s double and add 1.
而不是0 它就是加倍后再加1
But essentially it’s doubling.
但从本质上说 它是加倍了
Now the trouble is coming on the horizon as I can see
我现在可以看到的问题是
that if I just push that 0 bit over here,
如果我继续把这里的0移过来
I’m going to end up with 1010,
我最终将得到1010
and I know, it’s 10. Fine!
我知道 这是十进制里的10
But no, it’s hexadecimal!
但并不是这样 这是十六进制!
It’s not representable as a digit from 0 to 9.
它不能用0~9表示
So, what should you do then?
那么 你接下来应该怎么办?
Let it happen anyway and then look at it
如果什么都不做
and say: “Oh my golly, it’s gone to ten
你就会发现:天呐 到10了
it’s gone to eleven; it’s gone to fifteen even!
到11了 甚至到15了!
I’d better backtrack and undo it and then redo it?” No.
我要不撤销再重做一遍? 不用
Dive in early and reason as follows:
及早发现问题并按以下思路分析
Concentrate everybody! OK, what we want here
大家注意力集中!好了 在这我们希望
is for this thing to come out looking like
它的最终结果是
0001 0000.
0001 0000
Let’s say that’s the desired result.
这是我们想要的结果
Because that regarding these as BCD digits,
因为这些是BCD码
that’s 1 0, ten.
那是1和0 十进制的10
That’s exactly what you want.
恰好是你想要的结果
So how do we make that happen?
所以怎样才能得到这样的结果?
How do we make it carry over into this left-hand nibble here,
我们怎样使它移到左边的半字节中
when it doesn’t want to at the moment.
而不产生任何问题
So the fiendishly clever thing says:
所以有句很妙的话是这样说的:
Take a look at what you’ve currently got
看一看你现在有什么
because if what you got is 5 or more,
因为如果你现有的是5或更大的数字
the act of doubling it, it’s bound to get you into a number
把它加倍 你一定会得到一个
that needs to carry across.
需要转换的数字
So if it is going to cause you trouble, at 5 or more,
所以如果在5或更大数字的转换上有问题
we wanted to carry at 10,
我们希望能在10进位
it innately would like to carry at 16 and you don’t want that.
它本可以在16进位 但你不希望这样
David: What’s the difference, Sean, between 10 and 16?
肖恩 10和16之间差多少?
Sean: 6 David: 6. what’s half of that?
– 6 – 是6 它的一半是多少?
Sean: 3. David: All right. So, if we add three,
– 是3 – 是的 所以 如果我们加上3
the fact that we’re then shifting it
通过移动
will double our 3 contribution to 6,
会把3加倍成6
and we’ll make it carry.
我们就需要进位了
So the rule is, on Double Dabble,
所以在Double Dabble算法中
if what you see in your nibble
如果你在半字节中看到的
is 5 or more, then add 3.
是5或者比5更大的数 就再加3
So, here we go, look. Next stage now.
那么我们进入下一步
Because we’ve seen trouble on the horizon.
因为我们发现了错误
It’s 5, so add 3.
这是5 那就加上3
And 3, we agree, is 11.
我们都知道3是11
Now, here you do have to do a little addition with carries.
现在 你应该在转换过程中做一些加法
You can’t avoid it. Some carries will have to take place.
你不能回避这个问题 必须要进位
One and one is zero. Carry one.
1加1是0 进一个1
One and one is zero. Carry one.
1加1是0 再进一个1
One and one is zero. Carry one.
1加1是0 进一个1
The act of adding 3,
加3这个步骤
will make it look not like 0101,
会让它不再是0101
you’ve added the 3,
你加了3
it now looks like 1000. Magic!
它现在就是1000 好神奇!
But, what happens when you shift the final 0 in?
但是 当你将最后的0移进来后会怎样?
That 1 will shift left, into the left-hand nibble.
这个1将会移动到左边 移到左边的半字节中
And you’ll end up with: 0001 0000.
然后你将得到:0001 0000
And this thing is now empty.
这个半字节里就没有东西了
So you know you’ve come to the end of your conversion.
这你就完成了转换
It’s so cool. I love it dearly.
真是太酷了 我好喜欢它
You could argue though,
虽然你可能会认为
the one problem with all this is
这有个问题
that in order to do your shifts quickly, you’ve got this in a
为了更快地移动 你应该
sort of a unified shift register full of bits.
用统一的移位暂存器来移动这些字节
Your nibbles – in the end – end up looking correct.
你的半字节最终看似正确
But you’re gonna have to dig them out of the shift register.
但是你必须把他们移出移位暂存器
Oh yeah! It’s clearly.
这样就很清晰了
That’s a 4, yes. That’s a 2, isn’t it? Magic!
那是4 那是2 是吧?好神奇!
Of course, if you’re using this seriously,
当然 如果你仔细地运行这个过程
you have to try and generate these
你需要尝试更好地把它们
BCD digits
转成BCD码
in a way where they don’t necessarily need digging out of a bigger representation.
通过一种无须将它们移出移位暂存器的方法
But on the other hand you’re using that behind the scenes.
但另一方面你们确实用了这种方法
I’ve found, for you, the ultimate reference
我帮你们找了一些参考书
that I’ve taken this example from, and used the methodology.
我举的这个例子就来源于这本书 也用了书里的方法
It’s by a guy called Chuck Falconer.
它的作者是加克·福尔特纳
It’s actually referred to in the Wikipedia articles
维基百科上有关BCD码和Double Dabble的文章
on BCD and Double Dabble.
引用了该书中的内容
So we’ve pulled that over. It’s freely available.
我们把它收录了进来 它是完全免费的
You can go and dive in there to your heart’s content,
你可以好好地看一下它的内容
because he covers about how to make them [the nibbles] appear
因为他谈到了关于如何使用半字节
in a much more useable way.
让它发挥更大的作用
And what he also says is
同时他也提到
that when you start looking at this, you realize
如果你仔细思考 你会发现
you are actually doing
实际上 你是在做
the “division by ten and remainders” thing that we discussed.
我们讨论过的“除以10和余数”
But you’re doing it in a pretty efficient way
但你用了一种很高效的方式
and only occasionally needing that little addition of 3.
只需偶尔做一下加3的小加法
So that’s, I’m not saying there aren’t other ways
我并不是说没有其它的方法
This seems to be endless variants on this.
还有数不尽的方法
there’s signed BCD; there’s packed BCD; there’s all sorts.
有符号BCD法 压缩BCD法 还有其它很多
But if you just want to understand the fundamentals,
但如果你只是想明白基本原理
I would say go through the 42 example,
那我认为你要看前面关于42的例子
then go to Chuck Falconers memo.
和加克·福尔特纳的笔记
He does 255, as decimal,
他做了十进制的255
and boy that needs spotting problems
我的天 那需要从三组半字节
in about three sets of nibbles – not two.
而非两组半字节中找到问题
You have to spot one in the middle thing happening and so on.
你要关注运算过程中的问题
Sean: You mentioned 255, so this goes up to hundreds, thousand…?
你提到了255 所以它可以上百 上千?
David: Yes, yes. Sean: you just add more…?
-是的 是的 -你需要加…
You add more BCD digits on the left to cope.
你要在式子左边添加更多的BCD码来进行运算
But you give yourself a bigger problem
但是你给自己制造了一个更大的问题
When examining each of these digits
当你检验这些数字时
to see if they’re about to go beyond ten, when they’re doubled,
通过再一次向左移动 观察当它们加倍时
by shifting left one more time.
是否会超过10
You give yourself a bigger and bigger inspection task.
你的检验过程会越来越复杂
There’s no question.
这是毫无疑问的
So, like I said
如我所说
the Chuck Falconer memo from which this is derived,
我说的内容来自于加克·福尔纳特的笔记
we’ll put a link out to it. It is freely available.
我们会放一个链接 它是完全免费的
He doesn’t explain how
他没有解释
the people who invented this actually discovered it,
发明者到底怎么发现它的
worked out that it really does work.
是怎么研究它的原理的
It seems almost like magic when you do it.
当你运算的时候 它就像是魔法
And then, every so often I pull out another number
并且当我每次运算新数字时 我会想
and think I bet it won’t work for this
这方法不行
But it does. It’s quite incredible.
但是它可以 真是难以置信
So, there we are then. I think we’ve
就是这样 我认为
fairly well summarized now what the situation is,
我们已经很全面地做了讲解
that for great, big engineering, scientific calculations,
内容包括庞大的工程和科学计算
even for finding new prime numbers as huge integers,
甚至是寻找大整数形式的新质数
you really do need proper binary to speed things up.
你肯定需要合适的二进制来加速整个过程
But for some sorts of trivial calculations,
但是在做小型计算时
you might even want to do it in BCD all the time.
你甚至可能会想一直用BCD码进行运算
But even if you are basically binary and want to print out your answers,
但如果你想要用基础的二进制得出最终结果
you still have to convert from binary through to BCD.
你还是需要将二进制转换为十进制
And that is always a worry for the people who write the I/O routines,
写I/O程序的人 即写C语言之类的人
shall we say, for C and so on.
常常会担心
Is this gonna be efficient?
这会更加有效率吗?
What we’re saying is,
我们要说的是
at the computing end of things,
在所有运算的最后
you should be able to prepare that BCD-digit stream as quickly as possible.
你应该尽可能快地准备BCD码数字流
To finish off with them, life, the universe and everything,
来总结一下 生命 宇宙和所有的一切
will this work for converting 42?
它们对转换42有帮助吗?
Yes, it will.
当然 毋庸置疑
Now admittedly, here’s one I did early.
其实 这是我很早以前做的

发表评论

译制信息
视频概述

进制转换与编码的发展,对数学感兴趣的人会受益匪浅。

听录译者

Csy

翻译译者

ericaeureka

审核员

审核员TY

视频来源

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

相关推荐