【练习-055】批处理根据输入数求出cmd范围内最大次方数

CrLf

set /a n*=num,"max+=((n-1)>>31)+1","test=1/n/(!max!-max)"||goto re
这句用到了很多技巧，可读性降低，不过却是高效计算的核心代码，可读性在我看来一向是要排在高效、简洁、避免临时文件这几点之后的。

[ 本帖最后由 zm900612 于 2011-3-14 18:32 编辑 ]

CrLf

忽然想到这正是判断n是否为2的倍数的最快办法：set /a "test=1/(1073741824*n)"||echo %n%为2的倍数

qzwqzw

没办法台式机网络有点问题，使用手机回复比较累，简短点吧。关于溢出我不多讲，你测试下100000试试，看跟我的代码是否结果一致。

CrLf

已测试，100000结果为1，呵呵，有test的存在是不可能多次溢出的

qzwqzw

请测试你的乘法算法
我这里结果是2
除法算法天生不存在溢出问题我是知道的

qzwqzw

台式机网络刚恢复
set /a "test=1/(1073741824*n)"||echo %n%的技巧值得借鉴
不过乘法比较消耗CPU
改成“字节与”更好些
set /a "m=1/(n&1)"||echo %n%是偶数

CrLf

巧妙，位运算还是用得太少，没第一时间想到这方向

测试了下正算法，真的有溢出...而且十分诡异，为什么set /a n=100000*100000结果是1410065408？？溢出不是应该变成负数么？

CrLf

调试了一下，发现100000的溢出很奇怪，以下数据均为  【每次循环的n值   max值】：
请输入大于1的正整数：100000
100000             1
1410065408   2【100000*100000=1410065408？？？】
-1530494976  2

确切地说是大于46340（约等于极限值的开方）的数可能都有问题：

请输入大于1的正整数：46340
46340              1
2147395600   2
214822976     3【第三次循环时发生溢出，但是不转负】
-837484288    3
302580736     4

qzwqzw

没什么可怪异的，计算机的数集就像个圆，一个数不断累加，就像在圆上行走，等加到正数最大值时，就走了个半圆，再走一步就是负数最大值，然后继续延负数轴向前，直到走回零点，就画了一个整圆。然后重新开始，周而复始。类似于道家的阳极生阴，阴极生阳理论。数学上的数集也有类似的特性。溢出为正数不过是在数集圆上走的更远，越过了负数所在的半圆，又回到正数圆而已。不知道这样说你明白了没有？

CrLf

不敢苟同，个人见解如下：
溢出导致由正转负我可以理解，因为2147483647在cmd中的二进制形态为01111111111111111111111111111111，而-1则是1111111111111111111111111111110，所以数值计算时超过2147483648的部分会被当成负数，根本原因就是首位由0转1，才会正负逆转。
但是要发生逆转，必须达到1000000000000000000000000000000000000的数量级，可是有什么正数能同时满足下列方程组呢？
{m+n=32
m+n+n>64}

CrLf

哦，我晕，之前糊涂了，这里用的不是加而是乘，如果是加法确实不存在连续两次溢出，乘法溢出的可能就很大了

qzwqzw

抱歉，方程组没看懂
只看到二进制的-1写错了

不知道这样写如何？
二进制    十进制
00...0           0
00...1           1
......
01...1            2147483647
10...0            -2147483648
......
11...1            -1
00...0            0
......

CrLf

再理论化地解释一下：
假设计算范围为8位二进制00000000~11111111，也就是0~128，或者说-64~63，此时：

加法溢出：
十进制：64+64=128
二进制：1000000+1000000=10000000
十进制：65+65=130
二进制：1000001+1000001=10000010
发生溢出，由于二进制倒数第八位为1，所以由正转负，在cmd中分别变为-128和-126

乘法溢出：
十进制：64*64=4096
二进制：1000000*1000000=1000000000000
十进制：65*65=4225
二进制：1000001*1000001=1000010000001
两个算式的结果都超过11111111，于是发生溢出，只获取最后八位，也就是00000000和10000001，换算为cmd中的十进制分别为0与-127

所以结论是，当数值在n*2*128~(n*2+1)*128-1范围内时为正，而在(n*2-1)*128-1~(n*2+1)*128范围内时为负，不知道有没有讲错，反正大概意思是这样。
乘法之所以会出现同一个数值乘某数后，正数溢出仍为正数是因为数值前后跨度超过256，于是溢出之后再溢出，负负得正。这在加法中是不可能出现的，我之前脑筋歪了，把乘法当加法去了

[ 本帖最后由 zm900612 于 2011-3-14 21:34 编辑 ]

CrLf

正如27楼所言，咱俩说的恰恰是同一个事

qzwqzw

嗯，看着理论尤其是数字算式就头大如斗
只看到8位二进制的可表示范围错了（不好意思）
不是"0~128，或者说-64~63"
而是“0~256，或者说-128~127”