用加法实现减法 - 某公司笔试题

[Mingliang Zhu]

一个计算机系统包含以下原子操作：
1. 赋值
2. +1
3. 循环（确定次数的循环）
4. 只处理正整数和 0
5. 运算不会溢出

请在该系统上实现减法

--------------分隔符--------------

个人觉得关键是需要实现比较操作，比较 0 和非 0 很好实现（0 次循环），比较 1 以上就想不出来了……
不知各位大侠有什么思路的？

Best wishes,
Mingliang Zhu

[吴文金]

循环能 for (from i=a to b）吗？
吴文金
Joan Rivers  - "The first time I see a jogger smiling, I'll consider it."

2008/10/21 Mingliang Zhu <mingli...@gmail.com>

[Mingliang Zhu]

我觉得按题义似乎是不行
确定这个循环的次数需要计算 b-a

Best wishes,
Mingliang Zhu

2008/10/21 吴文金 <kevin...@gmail.com>:

[小马xioama]

如果行就很简单了。

2008/10/21 吴文金 <kevin...@gmail.com>

[Cao Yi]

循环是从小到大吧，然后每步加一，计数可知大减小是多少。

 

可是，这个计算机系统貌似不能比较两个数的大小吧，所以上面想到方式不能实做。

 

 

2008-10-21

---

Best Regards,

Cao Yi 

---

发件人： 吴文金

发送时间： 2008-10-21  11:12:56

收件人： pongba

抄送：

主题： [TopLanguage]_Re:_用加法实现减法_-_某公司笔试题

[Riskyer]

感觉关键是对题意的理解，确定次数的循环?是指不能人为控制循环次数而每次循环就要进行固定次数吗？如果这样，没有比较操作如何控制循环的次数呢？而且
只能处理正整数和0，那减法出现负数怎么处理？
感觉提议应该太明确一些

[alai]

楼主所说的"比较 0 和非 0 很好实现（0 次循环）"，能说说是怎样实现的吗？我怎么觉得这个也实现不了

2008/10/21 小马xioama <cnxi...@gmail.com>

[小马xioama]

控制循环的次数是原子操作里实现。确定次数的循环应该是如 a.times{ }这样的操作，其中a可以是一个正整数型变量。

2008/10/21 Riskyer <riche...@gmail.com>

[Dingding]

一个思路，供大家讨论。

首先实现自减一操作：
tmp = 0
result = 0
loop(n) {
result = tmp
tmp++
}
循环执行后result == n - 1

然后利用该操作作为原语实现任意数的减法操作（假定a>b）：
result = a
loop(b) {
dec(result)
}
循环执行后 result == a - b

On Oct 21, 11:04 am, "Mingliang Zhu" <mingliang....@gmail.com> wrote:
> 一个计算机系统包含以下原子操作：
> 1. 赋值
> 2. +1
> 3. 循环（确定次数的循环）
> 4. 只处理正整数和 0
> 5. 运算不会溢出
>
> 请在该系统上实现减法
>
> --------------分隔符--------------
>

> 个人觉得关键是需要实现比较操作，比较 0 和非 0 很好实现（0 次循环），比较 1 以上就想不出来了......

[Mingliang Zhu]

赞~~

Best wishes,
Mingliang Zhu

2008/10/21 Dingding <hank...@gmail.com>:

[小马xioama]

高手

2008/10/21 Dingding <hank...@gmail.com>

[星染流云]

a-b=c的话，不就是b再加上c个1等于a，而且题目中已经提供了“确定次数的循环”，直接用就可以了

mov (B,register)
mov (0,result)
WHILELOOP:
if (register < A) then
inc(result)
inc(register)
jmp WHILELOOP
endif

[小马xioama]

(register < A) 是不被系统支持的。

2008/10/21 星染流云 <xingra...@126.com>

[星染流云]

那个比较操作是隐含在循环里的，也可以不写出来。

确定次数的循环是系统提供的。如果没有比较操作，系统也没办法实现循环。

[小马xioama]

问题不是讨论系统怎么实现比较操作，而是用给定的原语实现减法功能。

2008/10/21 星染流云 <xingra...@126.com>

[星染流云]

我明白我哪里弄错了，我以为循环是loop(from,to)，其实应该是loop(N).，也就是loop(0,N)。那位解出的同学是高手。

[Davies Liu]

2008/10/21 Dingding <hank...@gmail.com>:

> 一个思路，供大家讨论。
>
> 首先实现自减一操作：
> tmp = 0
> result = 0
> loop(n) {
> result = tmp
> tmp++
> }

这部分还有问题，当 n 为 0 时还是 0

[小马xioama]

这部分问题不大，看下面一段

result = a
loop(b) {
   dec(result)
}

如果b=0, 那么直接返回a , a-b=a-0=0

如果a=0, 那么系统由于不支持负数，因此b也一定=0，返回还是0.

2008/10/21 Davies Liu <davie...@gmail.com>

[Len Kong]

> 2008/10/21 Dingding <hank...@gmail.com>:

> 一个思路，供大家讨论。
>
> 首先实现自减一操作：
> tmp = 0
> result = 0
> loop(n) {
> result = tmp
> tmp++
> }
> 循环执行后result == n - 1
>
> 然后利用该操作作为原语实现任意数的减法操作（假定a>b）：
> result = a
> loop(b) {
> dec(result)
> }
> 循环执行后 result == a - b
>

正解，应该就是这个思路，baidu的笔试题

[杨宏]

最近好多论坛和blog都在说这题


--
行到水穷处，坐看云起时

[王天一]

定义一个状态数组，开始全部置1，先从0加到a，每轮循环中变量+1，直到a-1，同时使对应的状态数组的元素置0；

后面的应该不用我说了吧，

最后统计还有多少个1

不知道有没有正确理解题目的意思。

2008/10/21 Mingliang Zhu <mingli...@gmail.com>

[小马xioama]

b在哪里出现？

2008/10/23 王天一 <jacklin...@gmail.com>

[王天一]

就是执行b次0变1的状态

2008/10/23 小马xioama <cnxi...@gmail.com>