laziness, impatience, and hubris PerlMonks

### Left shift operation done more than 32 times

by jesuashok (Curate)
 on May 21, 2006 at 05:23 UTC Need Help??

jesuashok has asked for the wisdom of the Perl Monks concerning the following question:

Dear fellow monks,

I can have an integer in Perl which exceeds 32 bits:

```for (\$i=0;\$i<60;\$i++) {
print "\$i: ";
print 1 << \$i;
print "\n";
}

Output :-
```0: 1
1: 2
2: 4
3: 8
4: 16
5: 32
6: 64
7: 128
8: 256
9: 512
10: 1024
11: 2048
12: 4096
13: 8192
14: 16384
15: 32768
16: 65536
17: 131072
18: 262144
19: 524288
20: 1048576
21: 2097152
22: 4194304
23: 8388608
24: 16777216
25: 33554432
26: 67108864
27: 134217728
28: 268435456
29: 536870912
30: 1073741824
31: 2147483648
32: 1
33: 2
34: 4
35: 8
36: 16
37: 32
38: 64
39: 128
40: 256
41: 512
42: 1024
43: 2048
44: 4096
45: 8192
46: 16384
47: 32768
48: 65536
49: 131072
50: 262144
51: 524288
52: 1048576
53: 2097152
54: 4194304
55: 8388608
56: 16777216
57: 33554432
58: 67108864
59: 134217728
I don't find any documentation which explains the above behaviour. Could anyone explain me the above.

"Keep pouring your ideas"

Replies are listed 'Best First'.
Re: Left shift operation done more than 32 times
by Zaxo (Archbishop) on May 21, 2006 at 05:35 UTC

It looks like, rather than overflow to all zeros, perl does \$i%32 before shifting. Math::BigInt behaves more like you expect:

```\$ perl -MMath::BigInt=:constant -e'print 1<<\$_,\$/ for 0..60'
1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
2147483648
4294967296
8589934592
17179869184
34359738368
68719476736
137438953472
274877906944
549755813888
1099511627776
2199023255552
4398046511104
8796093022208
17592186044416
35184372088832
70368744177664
140737488355328
281474976710656
562949953421312
1125899906842624
2251799813685248
4503599627370496
9007199254740992
18014398509481984
36028797018963968
72057594037927936
144115188075855872
288230376151711744
576460752303423488
1152921504606846976
\$

After Compline,
Zaxo

Re: Left shift operation done more than 32 times
by ikegami (Pope) on May 21, 2006 at 06:21 UTC

Which part is confusing?

The docs state that unsigned C integers are used when use integer is not used. 2147483648 * 2 is 4294967296, and 4294967296 doesn't fit in a 32 bit unsigned int (presuming you are using a 32 bit system). Therefore, this is an overflow situation.

Futhermore, the docs also state: "The result of overflowing the range of the integers is undefined because it is undefined also in C." That means 2147483648 << 1 can return anything, and you can't rely on it always returning 1.

You don't explain it. If you take the lower 32 bits of the result that's too big to fit into an integer, I expect the higher bits to be thrown away, and the lower bits kept. But the lower 32 bits of 4294967296 is 0, not 1.

I think Zaxo's reply is much closer to the truth.

If I do

```\$\ = "\n";
print 2147483648  << 1;
then I get 0. Even more:
```print +(2147483648+1) << 1;
yields 2.

I think Perl does both (edit: at least, on my platform): taking \$i%32 as its RHS, and drop the higher bits, just keeping the lower 32 bits, from the result.

I just wish jeshuashok's loop counter went a bit higher, to at least above 64.

I think Perl does both: taking \$i%32 as its RHS, and drop the higher bits, just keeping the lower 32 bits, from the result.
No, perl is doing exactly as it says in the docs; it is just using the underlying C << operator, whose result is undefined for overflows. That means the result will vary based on C compiler and/or CPU architecture.

from pp.c:

```    const IV shift = POPi;
if (PL_op->op_private & HINT_INTEGER) {
const IV i = TOPi;
SETi(i << shift);
}
else {
const UV u = TOPu;
SETu(u << shift);
}

Dave.

<q>You don't explain it.</q>

He explained it very exactly, _if_ you are familiar with the terminology of computer science. In computer science, when we say that the result of a particular operation is "undefined", we don't mean that you get the Perl value undef. (That would be the undefined _value_ -- this is the undefined _behavior_.) This terminology is older than Perl and means that in fact, depending on your compiler, your hardware architecture, your OS, your C libraries, and the phase of the moon, the result can and might very well be any of the following:

• 0
• 1
• -1
• 3
• 9827345908794823.74598723459879
• Your program crashes immediately.
• Everything seems fine at first, but your program crashes a few minutes later for no apparent reason.
• The entire operating system crashes. This result is unlikely under modern operating systems, unless the code with the undefined behavior is in kernel space or an important hardware driver (e.g., the video driver or a mass storage driver). Since Perl is seldom used for kernels or hardware drivers, this result is unlikely to be triggered by Perl code on modern systems.
• Other variables elsewhere in your program have their values changed without warning. (This particular result is unlikely in Perl, but the C library and compiler retain the right to do this if you do something the result of which is undefined behavior.)
• Small dragons fly out of your nose and attempt to re-enter your body elsewhere.
<q>If you take the lower 32 bits of the result that's too big to fit into an integer, I expect</q>

When it comes to undefined behavior, you don't get to have expectations.

Frankly I would prefer that Perl intercept such things and define their behavior, even if the definition is a fatal error that stops your program and prints a suitable error message. But it doesn't.

The long and short of it is that when the behavior is undefined that means the burden is on you, the programmer, to carefully avoid doing such things. If the result of doing left shift more than 32 times is undefined, then you must not do left shift more than 32 times -- or you must use a math library that defines it, such as the one mentioned in another reply.

Sanity? Oh, yeah, I've got all kinds of sanity. In fact, I've developed whole new kinds of sanity. Why, I've got so much sanity it's driving me crazy.
Which part is confusing?

Undefined behavior is inherently confusing and easily the worst thing about C (and that is really going some, because C has some pretty terrible characteristics). IMO the fact that Perl inherits some of it is... unfortunate.

Sanity? Oh, yeah, I've got all kinds of sanity. In fact, I've developed whole new kinds of sanity. Why, I've got so much sanity it's driving me crazy.
Re: Left shift operation done more than 32 times
by johngg (Canon) on May 21, 2006 at 11:22 UTC
I ran this out of interest on the Perl that comes with Solaris 10 SPARC edition, output from perl -V below

Running with a limit of 129 produces the following

```  0: 1
1: 2
2: 4
3: 8
4: 16
5: 32
6: 64
7: 128
8: 256
9: 512
10: 1024
11: 2048
12: 4096
13: 8192
14: 16384
15: 32768
16: 65536
17: 131072
18: 262144
19: 524288
20: 1048576
21: 2097152
22: 4194304
23: 8388608
24: 16777216
25: 33554432
26: 67108864
27: 134217728
28: 268435456
29: 536870912
30: 1073741824
31: 2147483648
32: 4294967296
33: 8589934592
34: 17179869184
35: 34359738368
36: 68719476736
37: 137438953472
38: 274877906944
39: 549755813888
40: 1099511627776
41: 2199023255552
42: 4398046511104
43: 8796093022208
44: 17592186044416
45: 35184372088832
46: 70368744177664
47: 140737488355328
48: 281474976710656
49: 562949953421312
50: 1125899906842624
51: 2251799813685248
52: 4503599627370496
53: 9007199254740992
54: 18014398509481984
55: 36028797018963968
56: 72057594037927936
57: 144115188075855872
58: 288230376151711744
59: 576460752303423488
60: 1152921504606846976
61: 2305843009213693952
62: 4611686018427387904
63: 9223372036854775808
64: 4294967296
65: 8589934592
66: 17179869184
67: 34359738368
68: 68719476736
69: 137438953472
70: 274877906944
71: 549755813888
72: 1099511627776
73: 2199023255552
74: 4398046511104
75: 8796093022208
76: 17592186044416
77: 35184372088832
78: 70368744177664
79: 140737488355328
80: 281474976710656
81: 562949953421312
82: 1125899906842624
83: 2251799813685248
84: 4503599627370496
85: 9007199254740992
86: 18014398509481984
87: 36028797018963968
88: 72057594037927936
89: 144115188075855872
90: 288230376151711744
91: 576460752303423488
92: 1152921504606846976
93: 2305843009213693952
94: 4611686018427387904
95: 9223372036854775808
96: 4294967296
97: 8589934592
98: 17179869184
99: 34359738368
100: 68719476736
101: 137438953472
102: 274877906944
103: 549755813888
104: 1099511627776
105: 2199023255552
106: 4398046511104
107: 8796093022208
108: 17592186044416
109: 35184372088832
110: 70368744177664
111: 140737488355328
112: 281474976710656
113: 562949953421312
114: 1125899906842624
115: 2251799813685248
116: 4503599627370496
117: 9007199254740992
118: 18014398509481984
119: 36028797018963968
120: 72057594037927936
121: 144115188075855872
122: 288230376151711744
123: 576460752303423488
124: 1152921504606846976
125: 2305843009213693952
126: 4611686018427387904
127: 9223372036854775808
128: 4294967296
129: 8589934592

Once we get beyond 63 shifts, the behaviour seems to be to cycle around the high order 32 bits. The behaviour may well be different for a Perl built with GCC rather than Sun's own compiler or with Solaris 10 on the Intel/AMD 64-bit architecture.

Cheers,

JohnGG

Re: Left shift operation done more than 32 times
by idsfa (Vicar) on May 21, 2006 at 05:37 UTC

At a guess, it has to do with using a 32-bit compiled version of perl (perhaps Win32???). Try recompiling with 64-bit integers.

The intelligent reader will judge for himself. Without examining the facts fully and fairly, there is no way of knowing whether vox populi is really vox dei, or merely vox asinorum. — Cyrus H. Gordon

Create A New User
Node Status?
node history
Node Type: perlquestion [id://550754]
Approved by Zaxo
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (4)
As of 2020-04-08 22:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The most amusing oxymoron is:

Results (46 votes). Check out past polls.

Notices?