Archived

This topic is now archived and is closed to further replies.

mr_jrt

Behaviour on BitShifting Overflow

Recommended Posts

I have found some confusing behaviour regarding bit shifting. When bits are left shifted into overflow, I have a big thick book by Mr H. Schildt thats says they will vanish into oblivion. He is quite clear that the shift is not a rotate, and that 0s are used to pad the value after the shift, unless its a negative signed integer, whereapon it gets a 1 to preserve the sign bit. However, this code contradicts this quite blatently:
  
#include <iostream>
using namespace std;

int main()
{
  unsigned int number = 255;
  unsigned int shift = 0;
  unsigned int result;

  do
  {
    result = number << shift;

    cout.setf(ios::hex, ios::basefield);
    cout.width(8);
    cout.fill(''0'');
    cout << result << " " << "shift:" << shift << endl;

    shift+=4;
  }while (shift < 64);
  
  return 0;
}
  
The output I get from it is this:
000000ff shift:0
00000ff0 shift:4
0000ff00 shift:8
000ff000 shift:c
00ff0000 shift:10
0ff00000 shift:14
ff000000 shift:18
f0000000 shift:1c
000000ff shift:20
00000ff0 shift:24
0000ff00 shift:28
000ff000 shift:2c
00ff0000 shift:30
0ff00000 shift:34
ff000000 shift:38
f0000000 shift:3c
Press any key to continue
 
That looks like a form of rotation to me, (admittedly, not very accurate until a complete wrap has occurred every 32 bits). I''m using VC++ (whose dissassembled code looks fine) on a P3 (btw, same results on another 2 tested P3s) Which is the correct behaviour, Herb''s way, or the way I''m getting atm?

Share this post


Link to post
Share on other sites
On MSVC7:

  
int main()
{
for(int shift=0; shift<64; shift++)
{
cout.setf(ios::hex, ios::basefield);
cout.width(8);
cout.fill(''0'');
cout << (1<<shift) << " " << "shift:" << shift << endl;
}
system("PAUSE");
}


Outputs:

00000001 shift:0
00000002 shift:1
00000004 shift:2
00000008 shift:3
00000010 shift:4
00000020 shift:5
00000040 shift:6
00000080 shift:7
00000100 shift:8
00000200 shift:9
00000400 shift:a
00000800 shift:b
00001000 shift:c
00002000 shift:d
00004000 shift:e
00008000 shift:f
00010000 shift:10
00020000 shift:11
00040000 shift:12
00080000 shift:13
00100000 shift:14
00200000 shift:15
00400000 shift:16
00800000 shift:17
01000000 shift:18
02000000 shift:19
04000000 shift:1a
08000000 shift:1b
10000000 shift:1c
20000000 shift:1d
40000000 shift:1e
80000000 shift:1f
00000001 shift:20
00000002 shift:21
00000004 shift:22
00000008 shift:23
00000010 shift:24
00000020 shift:25
00000040 shift:26
00000080 shift:27
00000100 shift:28
00000200 shift:29
00000400 shift:2a
00000800 shift:2b
00001000 shift:2c
00002000 shift:2d
00004000 shift:2e
00008000 shift:2f
00010000 shift:30
00020000 shift:31
00040000 shift:32
00080000 shift:33
00100000 shift:34
00200000 shift:35
00400000 shift:36
00800000 shift:37
01000000 shift:38
02000000 shift:39
04000000 shift:3a
08000000 shift:3b
10000000 shift:3c
20000000 shift:3d
40000000 shift:3e
80000000 shift:3f
Press any key to continue . . .


Which I think is wrong

Share this post


Link to post
Share on other sites
I believe you are invoking undefined behaviour in this example (I''ll admit I got the same results). If I remember correctly shifting by the size of the the variable or greater is considered undefined. I modified your code to avoid this and got the expected results:


  
#include <iostream>
using namespace std;
int main(){
unsigned int number = 255;
unsigned int loop;
for (loop = 0; loop < 16; loop++) {
if (loop) //don''t shift the first time!!

number = number << 4;
cout.setf(ios::hex, ios::basefield);
cout.width(8);
cout.fill(''0'');
cout << number << " " << "shift:" << loop*4 << endl;
}
return 0;
}


Output:

000000ff shift:0
00000ff0 shift:4
0000ff00 shift:8
000ff000 shift:c
00ff0000 shift:10
0ff00000 shift:14
ff000000 shift:18
f0000000 shift:1c
00000000 shift:20
00000000 shift:24
00000000 shift:28
00000000 shift:2c
00000000 shift:30
00000000 shift:34
00000000 shift:38
00000000 shift:3c

_____________________________

And the Phoenix shall rise from the ashes...

--Thunder_Hawk -- ¦þ
______________________________

Share this post


Link to post
Share on other sites
Yup, I just came back to share that same little nugget of annoying goodness with the community. Their reasoning is fair enough, but IMHO just setting the result to 0, or even doing the full 256 shifts would be more accurate than masking off bits.

Oh well, we have to work with what we''re given.

BTW, anyone know if it says in the standard that shifts > 32 should == 0, or is it left undefined?

Oh well. *sigh*

Share this post


Link to post
Share on other sites