qzwqzw

给出个求极大值的捷径：（此方法通用于所有二进制计算机）
通过二进制逻辑移位来给2开方，一直开到溢出，溢出后其结果是负的，以此负值判断结束条件。
@echo off &setlocal enabledelayedexpansion
for /l %%i in ...
applba 发表于 2011-4-27 09:41

求极值的方法很多
比如11楼的方法
如果非要用二进制移位，也可以这样

@echo off &setlocal enabledelayedexpansion
for /l %%i in  (1,1,256) do (
    set /a "_tmp=1<<%%i"
    if !_tmp! leq 0 (
        set /a "t2=%%i-1"
        set  /a "max=_tmp-1"
        goto 2out
    )
)
:2out
echo 2的!t2!次方最接近极大值!max!
pause>nul

applba

既然上面求了极大值，现在就不存在溢出问题了：

@echo off &setlocal enabledelayedexpansion
:input
cls
set /p _n=请输入正整数：
set /a  n=!_n!&&if  !n! lss 2 goto input
set  /a "varup=1,vardn=2147483647"
for /l %%i in (1,1,30) do (
        set /a "varup=!varup!*!n!,vardn=!vardn!/!n!"
        set /a "var=!vardn!/!varup!"
        if !var! lss !n! (
                if !var! equ 0 (set /a "cnt=2*%%i-1" && goto out)
                set /a "cnt=2*%%i" && goto out
        )
)
:out
echo !n!的!cnt!次方接近最大值！
PAUSE&goto input
复制代码

思路也很简单，正反一起用，往中间碰撞……

applba

给出个求极大值的捷径：
通过二进制移位来给2开方，一直开到溢出，溢出后其结果是负的，以此负值判断结束条件。

@echo off &setlocal enabledelayedexpansion
for /l %%i in  (1,1,256) do (
    set /a "_tmp=1<<%%i"
    if !_tmp! leq 0 (
        set /a "t2=%%i-1"
        set  /a "max=((1<<!t2!)-1)+(1<<!t2!)"
        goto 2out
    )
)
:2out
echo 2的!t2!次方最接近极大值!max!
pause>nul
复制代码

我用for是和256是因为我还没有看到支持256bit数据类型的编程语言和操作系统……
当然你喜欢用goto也没什么问题的……

CrLf

嗯，笔误，呵呵&nbsp;

qzwqzw

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

CrLf

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

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 编辑 ]

qzwqzw

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

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

CrLf

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

CrLf

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

qzwqzw

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

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

CrLf

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

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

qzwqzw

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

qzwqzw

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