符号扩展与按位移位运算 [英] Sign extension with bitwise shift operation
问题描述
以下<一个href=\"http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array\">this Q&安培; A我想考试的答案,所以我写了:
的#include&LT;&stdio.h中GT;诠释的main()
{ 诠释吨; INT I;
对于(i = 120; I&LT; 140;我++){
T =(I - 128)GT;&GT; 31;
的printf(T =%X,I-128 =%X,〜T&安培; I =%X,〜T =%X \\ n,T,I-128,(〜T&安培; I)〜T) ;
} 返回0;
}
和输出是:
T = FFFFFFFF,I-128 = FFFFFFF8,〜T&安培; I = 0,〜t = 0的
T = FFFFFFFF,I-128 = FFFFFFF9,〜T&安培; I = 0,〜t = 0的
T = FFFFFFFF,I-128 = FFFFFFFA,〜T&安培; I = 0,〜t = 0的
T = FFFFFFFF,I-128 = FFFFFFFB,〜T&安培; I = 0,〜t = 0的
T = FFFFFFFF,I-128 = FFFFFFFC,〜T&安培; I = 0,〜t = 0的
T = FFFFFFFF,I-128 = FFFFFFFD,〜T&安培; I = 0,〜t = 0的
T = FFFFFFFF,I-128 = FFFFFFFE,〜T&安培; I = 0,〜t = 0的
T = FFFFFFFF,I-128 = FFFFFFFF,〜T&安培; I = 0,〜t = 0的
t = 0时,I-128 = 0,〜T&放大器; I = 80〜T = FFFFFFFF
t = 0时,I-128 = 1〜T&安培; I = 81〜T = FFFFFFFF
t = 0时,I-128 = 2,〜T&放大器; I = 82〜T = FFFFFFFF
t = 0时,I-128 = 3〜T&安培; I = 83〜T = FFFFFFFF
t = 0时,I-128 = 4〜T&安培; I = 84〜T = FFFFFFFF
t = 0时,I-128 = 5,〜T&放大器; I = 85〜T = FFFFFFFF
t = 0时,I-128 = 6,〜T&放大器; I = 86〜T = FFFFFFFF
t = 0时,I-128 = 7,〜T&放大器; I = 87〜T = FFFFFFFF
t = 0时,I-128 = 8,〜T&放大器; I = 88〜T = FFFFFFFF
t = 0时,I-128 = 9〜T&安培; I = 89〜T = FFFFFFFF
t = 0时,I-128 = A,〜T&安培; I = 8A,〜T = FFFFFFFF
t = 0时,I-128 = B,〜T&安培; I = 8B,〜T = FFFFFFFF
为什么〜牛逼
中的任何负数 -1 == 0xFFFFFFFF的
如果 ŧ
声明为整数?
来源:右用C 转向负数
编辑:据该科最新的标准草案,关于负数这种行为是依赖于实现:
E1 >> E2的结果是E1右移E2位的位置。如果E1有一个无符号类型,或者如果E1有一个签名的类型和一个非负值,则结果的值是E1 / 2 E2 的商的整数部分。如果E1有一个签名的类型和负值,所得到的值是实现定义块引用>和,你的实现是可能做有两个补数算术移位
运营商
&GT;&GT;
为签名右移或算术右移,却将所有的位向右一个指定的次数。重要的是&GT;&GT;
填充最左边的符号位(最高有效位MSB)到最左边位后移。这就是所谓的符号扩展的和用于的 preserve符号的负数,当你转移他们的权利。下面是我的图解再presentation用一个例子来说明其工作原理(一字节):结果
例如:I = -5&GT;&GT; 3;移位位右三时
在五二补的形式为
1111 1011
内存重新presentation:MSB
+ ---- + ---- + ---- + --- + --- + --- + --- + --- +
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
+ ---- + ---- + ---- + --- + --- + --- + --- + --- +
7 6 5 4 3 2 1 0
^这第七个,最左边位为符号位及以下,如何
&GT;&GT;
作品?当你做-5&GT;&GT; 3
这3个位移
并损失
MSB(___________)
+ ---- + ---- + ---- + --- + --- + --- + --- + --- +
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
+ ---- + ---- + ---- + --- + --- + --- + --- + --- +
| \\ \\
| ------------ | ---------- |
| | |
▼▼▼
+ ---- + ---- + ---- + --- + --- + --- + --- + --- +
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+ ---- + ---- + ---- + --- + --- + --- + --- + --- +
(______________)
该标志是
传播注意:最左边的三位是一个,因为在每个班次符号位为preserved和每个位是正确的了。我写的符号传播的,因为这一切的三位是因为符号(而不是数据)。
【答案】结果
你的输出
在前八行
〜t为0
==&GT; t是FFFFFFFF
==&GT; t为-1(注意: 2的-1补是
FFFFFFFF
,因为1 = 00000001
,1的补1是FFFFFFFE
,2的补码= 1的补+ 1即:FFFFFFFE
+00000001
=FFFFFFFF
的)所以
T
总是在第一循环八次评估1
。 是如何?在for循环
为(i = 120; I&LT; 140;我++){
T =(I - 128)GT;&GT; 31;
的i值
对于前八时间I = 120,121,122,123,124,125,126,127
所有八个值的小于128 的。于是返回的(I - 128)= -8,-7,-6,-5,-4,-3,-2,-1
。因此,在第一八次前pressionT =(I - 128)GT;&GT; 31
移权利负数。T =(I - 128)GT;&GT; 31
T = -ve号&GT;&GT; 31由于系统中的int是4字节= 32位,所有的最右边的
31
位移出和损失的由于符号位传播这是1
为负数所有位值变为1
的。 (如我如上图所示为一个字节)因此,对于拳头八次:
T = -ve号&GT;&GT; 31 == -1
T = -1
由此给
〜T = 0因此拳头输出八次〜t为0。
剩余最后几行
〜t是FFFFFFFF
==&GT; 〜t为-1
==&GT; t为0有关剩余的最后一行,在循环
为(i = 120; I&LT; 140;我++){
T =(I - 128)GT;&GT; 31;我值
128,129,130,132,133,134,135,136,137,138,139,
的都是大于或等于到的128和符号位为0
。所以(I - 128)剩余的最后几行是
&GT; = 0
键,这一切的MSB符号位=0
。而且因为你又向右移动31次的所有位节选然后感叹位移出并签署位0
传播和填充所有位与0
和幅度变0
。我认为这将是很好的,如果我写一个例子为正数了。因此,我们举一个例子
5 GT;&GT; 3
五是一个字节0000 0101
这3个位移
并损失
MSB(___________)
+ ---- + ---- + ---- + --- + --- + --- + --- + --- +
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
+ ---- + ---- + ---- + --- + --- + --- + --- + --- +
| \\ \\
| ------------ | ---------- |
| | |
▼▼▼
+ ---- + ---- + ---- + --- + --- + --- + --- + --- +
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+ ---- + ---- + ---- + --- + --- + --- + --- + --- +
(______________)
该标志是
传播再次见我写的符号传播的,所以最左边的三个零是由于签位。
因此,这是运营商
&GT;&GT;
签名右移做的,和 preserves符号左操作数。following this Q&A I tried to exam the answer so I wrote:
#include <stdio.h> int main () { int t;int i; for (i=120;i<140;i++){ t = (i - 128) >> 31; printf ("t = %X , i-128 = %X , ~t & i = %X , ~t = %X \n", t, i-128 , (~t &i), ~t); } return 0; }
and the Output is:
t = FFFFFFFF , i-128 = FFFFFFF8 , ~t & i = 0 , ~t = 0 t = FFFFFFFF , i-128 = FFFFFFF9 , ~t & i = 0 , ~t = 0 t = FFFFFFFF , i-128 = FFFFFFFA , ~t & i = 0 , ~t = 0 t = FFFFFFFF , i-128 = FFFFFFFB , ~t & i = 0 , ~t = 0 t = FFFFFFFF , i-128 = FFFFFFFC , ~t & i = 0 , ~t = 0 t = FFFFFFFF , i-128 = FFFFFFFD , ~t & i = 0 , ~t = 0 t = FFFFFFFF , i-128 = FFFFFFFE , ~t & i = 0 , ~t = 0 t = FFFFFFFF , i-128 = FFFFFFFF , ~t & i = 0 , ~t = 0 t = 0 , i-128 = 0 , ~t & i = 80 , ~t = FFFFFFFF t = 0 , i-128 = 1 , ~t & i = 81 , ~t = FFFFFFFF t = 0 , i-128 = 2 , ~t & i = 82 , ~t = FFFFFFFF t = 0 , i-128 = 3 , ~t & i = 83 , ~t = FFFFFFFF t = 0 , i-128 = 4 , ~t & i = 84 , ~t = FFFFFFFF t = 0 , i-128 = 5 , ~t & i = 85 , ~t = FFFFFFFF t = 0 , i-128 = 6 , ~t & i = 86 , ~t = FFFFFFFF t = 0 , i-128 = 7 , ~t & i = 87 , ~t = FFFFFFFF t = 0 , i-128 = 8 , ~t & i = 88 , ~t = FFFFFFFF t = 0 , i-128 = 9 , ~t & i = 89 , ~t = FFFFFFFF t = 0 , i-128 = A , ~t & i = 8A , ~t = FFFFFFFF t = 0 , i-128 = B , ~t & i = 8B , ~t = FFFFFFFF
Why does
~t
of any negative number is-1 == 0xFFFFFFFF
ift
declared as integer ?解决方案From: Right shifting negative numbers in C
Edit: According to the Section 6.5.7 of the latest draft standard, this behavior on negative numbers is implementation dependent:
The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.And, your implementation is probably doing an Arithmetic Shift with two's complement numbers
Operator
>>
as Signed right shift or arithmetic right shift, shift all the bits to right a specified number of times. Important is>>
fills leftmost sign bit (Most Significant Bit MSB) to leftmost bit the after shift. This is called sign extension and serves to preserve the sign of negative numbers when you shift them right.Below is my diagrammatic representation with an example to show how this works (for one byte):
Example:i = -5 >> 3; shift bits right three time
Five in two's complement form is
1111 1011
Memory Representation:MSB +----+----+----+---+---+---+---+---+ | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | +----+----+----+---+---+---+---+---+ 7 6 5 4 3 2 1 0 ^ This seventh, the left most bit is SIGN bit
And below is, how
>>
works? When you do-5 >> 3
this 3 bits are shifted out and loss MSB (___________) +----+----+----+---+---+---+---+---+ | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | +----+----+----+---+---+---+---+---+ | \ \ | ------------| ----------| | | | ▼ ▼ ▼ +----+----+----+---+---+---+---+---+ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | +----+----+----+---+---+---+---+---+ (______________) The sign is propagated
Notice: the left most three bits are one because on each shift sign bit is preserved and each bit is right too. I have written The sign is propagated because all this three bits are because of sign(but not data).
[ANSWER]
In your output infirst Eight lines
~t is 0 ==> t is FFFFFFFF ==> t is -1
(Note: 2's complement of -1 is
FFFFFFFF
, because1 = 00000001
, 1's complement of 1 isFFFFFFFE
, and 2's complement = 1's complement + 1 that is:FFFFFFFE
+00000001
=FFFFFFFF
)So
t
is always evaluated-1
in first eight times in loop. Yes, How ?In for loop
for (i=120;i<140;i++){ t = (i - 128) >> 31;
values of
i
for first eight time isi = 120, 121, 122, 123, 124, 125, 126 ,127
all eight values are less then 128. So return of(i - 128) = -8, -7, -6, -5, -4, -3, -2, -1
. hence in first eight times expressiont = (i - 128) >> 31
shift-rights a negative number.t = (i - 128) >> 31 t = -ve number >> 31
Because in your system int is of 4 bytes = 32 bits, all right most
31
bits are shift-out and loss and due to propagation of sign bit that is1
for negative number all bits value becomes1
. (as I have shown in above figure for one byte)So for fist eight times:
t = -ve number >> 31 == -1 t = -1 and this gives ~t = 0
Hence output of fist eight times for ~t is 0.
For remaining last lines
~t is FFFFFFFF ==> ~t is -1 ==> t is 0
For remaining last lines, in for loop
for (i=120;i<140;i++){ t = (i - 128) >> 31;
i values are
128, 129, 130, 132, 133, 134, 135, 136, 137, 138, 139,
all are greater then or equals to 128. and sign bit is0
.So (i - 128) for remaining last lines is
>=0
and for all this MSB sign bit =0
. And because again you shifts right 31 times all bits excepts then sigh bit shift-out and sign bit0
propagates and fills all bits with0
and magnitude becomes0
.I think it would be good if I write an example for a positive number too. So we take an example
5 >> 3
and five is one byte is0000 0101
this 3 bits are shifted out and loss MSB (___________) +----+----+----+---+---+---+---+---+ | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | +----+----+----+---+---+---+---+---+ | \ \ | ------------| ----------| | | | ▼ ▼ ▼ +----+----+----+---+---+---+---+---+ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | +----+----+----+---+---+---+---+---+ (______________) The sign is propagated
See again I writes The sign is propagated, So leftmost three zeros are due to sign bit.
So this is what operator
>>
Signed right shift do, and preserves the sign of left operand.这篇关于符号扩展与按位移位运算的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!