正文

程序设计中的位移指令2008-01-15 18:56:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/niao0311/32217.html

分享到:

事情的起因是因为一小段汇编程序,其中关键的几条指令如下:
mov ax,34h
loop2:mov bx,0ffffh
loop1:mov cx,0ffffh
next:mul al,2//关键语句,进行乘法操作
loop next
dec bx
jnz loop1

    编译和连接通过后,程序运行需要时间14秒,而将其中的关键语句由乘法换为移位指令时,即关键语句变为 Shl al,1
    编译和连接通过后,程序运行需要时间4秒。
    众所周知,左移一位和乘2的操作结果是一样的,都是将原操作数扩大了一倍,那为什么将乘法操作换为移位指令后,操作效果会相差这么大呢?可能大家也已经想到了答案,移位指令的速度比乘法指令的快,那为什么产生相同结果的移位指令和乘法指令在速度上会有如此大的差异呢?下面我们从移位器和乘法器的逻辑电路设计的角度来分析一下这个问题。
    图1所示的是一个四位移位寄存器的原理图,有四个D边沿触发器构成,di是移位器的串行输入,Do是移位器的串行输出,Cp 是移位脉冲信号,Di=Qi-1每个移位寄存器的输出端作为下一个移位寄存器的输入端。


    图1 用D触发器构成的四位移位寄存器

    当di=1011时移位脉冲与各个触发器输出的关系如下表所示:


Cp 顺序

移位寄存器中的数据

Q1

Q2

Q3

Q4

0

0

0

0

0

1

0

0

0

1

2

0

0

1

0

3

0

1

0

1

4

1

0

1

1

图2 脉冲cp与移位寄存器关系表


   
当cp=4时,移位寄存器中的数据,正好等于输入数据,q4输出的数据等于输入的数据。
    我们知道,计算机是用二进制表示数据的,用二进制很容易的进行加法,减法运算,但是怎样进行乘法运算呢?在十进制的运算中,我们很容易的得到相乘的结果,但是在二进制中,相乘就变成了一件很复杂的事情,因为二进制是无法表示乘法和除法操作的,我们只能用加法或减法来代替。
    当我们在十进制中计算z=x*y时,我们可以将它转化成z=x+x+…+x(y个)来计算,其实在二进制中,我们也是这样计算的。不过对于用二进制表达的数来说,其乘法规则更为简单一些:从乘法y 的最低位开始,若这一位为“1”,则将被乘数x 写下;若这一位为“0”,则写下全0。然后再对乘数y的高一位进行的乘法运算,其规则同上,不过这一位乘数的权与最低位乘数的权不一样,因此被乘数x 要左移一位。依次类推,直到乘数各位乘完为止,最后将它们统统加起来,便得到最后乘积z
    图3所示的是乘法逻辑结构原理图,其中有三个寄存器,其中 R0 存放部分积z,R1 寄存器存放乘数y,R2寄存器存放被乘数x。另外还需一个加法器和一个计数器,前者完成部分积与位积的累加,后者对移位的次数进行计数,以便判断乘法运算是否结束。
    乘法开始时,“启动”信号使控制触发器 Cx 置“1”,于是开启时序脉冲 T 。当乘数寄存器 R0 最末位为“1”时,部分积 z 和被乘数 x 在加法器中相加,其结果输出至 R0 的输入端,一旦打入控制脉冲 T,控制信号 LDR0 使部分积右移 1 位,与此同时,乘数寄存器 R1 也在控制信号 LDR1 作用下右移一位,且计数器i计数 1 次。当计数器 i = n 时,计数器i的溢出信号使控制触发器 Cx 置“0”,关闭时序脉冲T,乘法操作结束。


                       
                                             图3 乘法逻辑结构原理图

    从上面的介绍中,我们可以很清楚的得到结论移位操作比乘法操作的运算速度快,他们之间的差异可以通过8086的汇编指令来比较, 在8086的指令系统中,乘法操作需要8~13个机器周期,而移位操作只需要2~3个机器周期。虽然现在的乘法器已经有了很大的改进,但只能减小他们之间的速度差距,而无法达到相同的效果。
    并不是所有的乘法操作都可以转化移位操作的,由于移位器的位数与系统的位数是一样的,所以操作数的位数是不能超过系统位数长度的,由于8086是8位机,所以操作数的位数不能超过8,我们常用的计算机都是32位机,移位操作只对short,int,char,long类型的数据有作用,因为他们分别为1字节、2字节、1字节、4字节。
    对char和short 移位运算时(不论左移还是右移),char和short 都先被自动提升到int型。再执行移位运算。如果char和short为负数的时候,也就是说符号位也要扩展,高位全部用1填充,随后再做移位!

例如:
Short b=01000000;
int i;
i=b<<2;
//结果为256,2进制为00000001 00000000
b=(short)(b<<2);//结果为0, short只有8位,高位被截断
再如: short b=11111111;//十进制为-1
b=( short)(b<<2);
//变为11111111 11111100,10进制为-4
b=( short)(b>>2);
//变为11111111 11111111,10进制为-1
b=( short)(b>>>2);
//变为00111111 11111111,b还是-1,因为b先被扩展为int型
注意:左移(<<)时,如果将1移进高位那么值就变为负的。
高位移出,低位补0
右移运算(>>):低位移出,高位填充原来高位的值。
无符号右移(>>>):低位移出,高位用0填充。
有这样一段代码:
#i nclude <stdio。h>
void main()
{
unsigned int i,j;
i=35;
//为什么下面两个左移操作结果不一样?
j=1<<i;// j为8
j=1<<35;// j为0
}
    为什么会产生这样的情况呢? 原因是这样的:i=35;j=1<<i;这两句在C没有做优化的情况下,将被编译成下面的机器指令:
mov dword ptr [i],23h
mov eax,1
mov ecx,dword ptr [i]
shl eax,cl
mov dword ptr [j],eax
    在shl一句中,eax=1,cl=35。而Intel CPU执行shl指令时,会先将cl与31进行and操作,以限制左移的次数小于等于31。因为35 & 31 = 3,所以这样的指令相当于将1左移3位,结果是8。
    而j=1<<35;一句是常数运算,VC即使不做优化,编译器也会直接计算1<<35的结果。VC编译器发现35大于31时,就会直接将结果设置为0。
    所以, 移位操作不要超过界限,否则,结果是不可预期的。
    在很多大的情况下,我们是不能直接应用移位操作的,比如x=x*10,我们不能将x移位n次就得到新的结果,但2是2的1次幂,8是2的3次幂,2+8=10,我们可以利用两次位移加一次加法来得到计算结果。诸如此类的例子不胜枚举, 512+128=640, 512+256+32=800…。多数情况下我们都可以将乘法操作换成位移操作。
    从上面的介绍中,我们可以了解到移位指令的具体操作,更可以认识到在程序设计中的意义。作为一名优秀的程序员,我们应该注意程序的执行效率,使程序得到最大程度的优化,特别是在处理海量数据的时候,这就变得非常必要。移位指令作为系统指令的一部分,可以在一定程度上帮助我们实现复杂的数值运算,而不会增加系统负担,这是非常有意义的。

阅读(3252) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册