Left shift operation done more than 32 times

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

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 $ [download] After Compline, Zaxo	[reply] [d/l]
Re: Left shift operation done more than 32 times by ikegami (Patriarch) 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.	[reply] [d/l] [select]
Re^2: Left shift operation done more than 32 times by bart (Canon) on May 21, 2006 at 07:20 UTC
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;` [download] then I get `0`. Even more: `print +(2147483648+1) << 1;` [download] 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.	[reply] [d/l] [select]
Re^3: Left shift operation done more than 32 times by dave_the_m (Monsignor) on May 21, 2006 at 09:20 UTC
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); }` [download] Dave.	[reply] [d/l]
Re: Left shift operation done more than 32 times by jonadab (Parson) on May 21, 2006 at 11:12 UTC
<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.	[reply]
Re: Left shift operation done more than 32 times by jonadab (Parson) on May 21, 2006 at 11:34 UTC
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.	[reply]
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 Read more... (4 kB) 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 [download] 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	[reply] [d/l] [select]
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	[reply]


Clear questions and runnable code get the best and fastest answer
	PerlMonks