不用除法怎么求A/3

mci2004

Ager 发表于 2012-10-22 23:53
@mci2004
@发仔很忙

我就是在我的电脑上测试过，才质疑正确性的。我用的是 gcc4.4.3 linux  64
一开始我没意识到自己的电脑是64位的，所以用循环中用32产生了问题。后来，我改成64还是有问题，例如50/3 会得到一个错误值.....
哦，我明白了，根本没考虑不能整除的情况。

大神，现在可以解释下了吗？

1，依据什么数学知识？
2，return (-p)，为什么是-p，跟平台相关？

cjaizss

发仔很忙 发表于 2012-10-21 20:57
今天看到一个题目，说的是一个32位整数A，要求不用除法，怎么求A/3？

这让我想到从朋友那里听到的一个问 ...

1/3在二进制下表示是
0.(01)
然后你明白该怎么做了

evaspring

好贴，留名 ~

Ager

@mci2004
@发仔很忙

下面，我来讲解一下原理。

请注意，在接下来的讲解中：

（1）具体的过程依赖于具体的实现，但目前大多数平台在这方面的原理都差不多，很容易类推。

（2）原理的推演，都是直觉式的，而没有按照严格的数学方法。当然，这些直觉的结论是可以得到严格的数学方法证明的，而这种证明，在绝大多数的数学课本中都可以找到。

我们的目标：

X = A / 3

最最首先，我们考虑整数1，我们知道：

1 = 0.999999999999..........（无穷个数字9）

上式 = 9 x 0.111111111111........（无穷个数字1）

又因为 1= 9 x (1/9)，所以，我们的直觉是：

1/9 = 0.111111111111........

而0.111111111111........ = 0.1 + 0.01 + 0.001 + 0.0001 + ......................

即，1/9 = 1/10 + 1/100 +  1/1000 +  1/10000 + ......................

那么，由直觉，我们得到：

1/n =  1/(n+1) + 1/(n+1)^2 + 1/(n+1)^3 + 1/(n+1)^4 + ......................

（这一点，可以由严格的数学方法来证明，证明略。）

那么，就有：

1/3 =  1/4 + 1/4^2 + 1/4^3 + 1/4^4 + ......................

也就是：

1/3 =  1/2^2 + 1/2^4 + 1/2^6 + 1/2^8 + ......................

那么，就有：

X = A / 3 =  A/2^2 + A/2^4 + A/2^6 + A/2^8 + ......................

现在，数学方法出来了，我们的基本思路就有了：

一个整数A，要求被3除的商，可以由A除以4、A除以16、A除以64、A除以256、……的累加得到。

我们知道，如果将整数A表示为位向量，那么它除以2所得到的商数，可以由其位向量经过“向右移动1位”操作所得到的位向量来表示。

粗略地说，就是（在整数的视角下）：

A/2 = A>>1
A/4 = A>>2 (*)
A/8 = A>>3
A/16 = A>>4 (*)
A/32 = A>>5
A/64 = A>>6 (*)
A/128 = A>>7
A/256 = A>>8 (*)
……
(*)表示我们需要的。每一个阶段，在“>>”右边的操作数分别是：2、4、6、8、…… 2i，for Integer i = 2 to 某个上限。

但是，仔细思考一下，我们就会意识到：这种“向右移动1位”的方法，根本行不通！

为什么？

1/n =  1/(n+1) + 1/(n+1)^2 + 1/(n+1)^3 + 1/(n+1)^4 + ......................

—— 这种方法能够成立，是建立在等号后面的“各项所组成的序列是*收敛的*”这个基础上的，而这种收敛的趋势必须是十分准确的（各项越来越精细），也就意味着它们是越来越小的小数。但是，我们利用“向右移动1位”这种方法，根本就得不到这种越来越精细的小数。

既然是这样 …… 那么，我们的思路就要来个180度的大转捩！

“向右移动1位”得到越来越精细的小数行不通，我们就用“向左移动1位”得到越来越大的整数，也就是得到A*4、A*16、A*64、A*256……这样的整数。可以肯定，在达到某个上限之前，这些“大整数”必然都是准确的。

说到这里，你恐怕要认为我是发疯了！明明是需要越来越小的小数，我却在这里搞越来越大的整数，这不是彻底的南辕北辙了吗？！

是的，我的确就是要这麽做，而且不但如此，就像那些越来越小的小数将被累加起来一样，我搞的这些越来越大的整数，也要被累加起来！

疯了疯了，Ager 已经彻底疯了 ……

把程序跑一下吧 —— 但有个非常悲哀的约束：A只能是3的整倍数，也就是说X=A/3必须是一个满足整除的式子（若非如此即会得到一个"奇怪的"答案）。

—— 结果肯定是没错的，而且对于负整数，结果也一样正确。

这是为什么呢？

以下纯属乱扯，仅供参考 ……

（1）计算机本身，根本不知道“>>”（向右移位）意味着“除以2”，也根本不知道“<<”（向左移位）意味着“乘以2” —— 在计算机本身看来，根本就没有这种“意味”。它根本没有“收敛”、“发散”、“大”、“小”这些概念。对于它来说，内部的一个位向量，被“>>”或是被“<<”，只是移位的方向不同而已。

（2）非常概略地说：你从左向右看一个位向量是整数，那么也可以从右向左看它是小数。

（3）加法没有改变。

（4）在加法下，位向量中的“最低位”的所谓“有效信息”始终被正确地计算与保留，正如：对一个分数中接近小数点的小数部分做加法，会保持相当的正确性。

（5）对于古人观念中的“方正平直的大地”来说，南辕北辙当然是错误的。但对于有“闭合的赤道”观念的航海家来说，向东与向西虽然方向不同，但最终都是可以到达目的地的。或者说，顺着任何一条纬线一直朝正前方走下去，只要行程超过该纬线的周长，就必然会经过原点。

mci2004

回复 24# Ager

    等比数列前N项和？我之前也想到了，但是没你这么严谨的推到过程，学习了。
   
    谢谢了，mark一下一会仔细研究。

Musikk_P3

Ager 发表于 2012-10-25 22:56
@mci2004
@发仔很忙


说到这里，你恐怕要认为我是发疯了！明明是需要越来越小的小数，我却在这里搞越来越大的整数，这不是彻底的南辕北辙了吗？！

是的，我的确就是要这麽做，而且不但如此，就像那些越来越小的小数将被累加起来一样，我搞的这些越来越大的整数，也要被累加起来！

疯了疯了，Ager 已经彻底疯了 ……

我也觉得，高人你的确疯了，至少是疯狂了……