TalkChess.com

The value of a right-shift expression e1 >> e2 is e1 / 2^e2, and the value of a left-shift expression e1 << e2 is e1 * 2^e2.

My question is what practically happens when these values are out of bound.

let say we have bitboards that are unsigned 64 bits variables.
I have array setmask for all the 64 powers of 2 when setmask=2^i for 0<=i<=63

1)What is the value of (setmask[a]<<b) when a+b>=64
I find that it is 0 in my system.
Can I trust it to be always 0?

2)What is the value of (setmask[a]>>b) when b>a
I find that it is 0 in my system in the examples that I tried.
Can I trust it practically to be always 0.

3)Can I be sure that the following rules always exist?
(a|b)<<c=(a<<c)|(b<<c)
(a|b)>>c=(a>>c)|(b>>c)

I think that it is logical to have all these rules with all compilers but the question is if it really happens.

I think that these rules can clearly make programming more simple because if pushing squares to some direction is out of the board then it clearly intersects nothing and can be considered as 0.

Not every out of the board is translated to something like this
but at least pushing piece to file that does not exist can be translated to 0 if you use h1=56,...h8=63(or pushing piece to rank that does not exist can be translated to 0 if you use a8=56,...h8=63)

Uri

1.) is always zero, as well as 2.) as long as you shift logical right (unsigned) and 'b' is less 64. Also shift is distributive over 'or', 'xor' and 'and'.

But note if a + b >= 64, (1 << a) << b might not equal to 1 << (a+b), since x86/64 implicitly applies modulo 64 (aka and 63) with the shift amount. Thus, shift right/left with 64 doesn't clear a register, but leaves it constant. I think that is not fully specified in C/C++ but might vary on different processors.

Not the best source, but anyways, from Microsoft's help:

"The results are undefined if the right operand of a shift expression is negative or if the right operand is greater than or equal to the number of bits in the (promoted) left operand."


In other words, if you shift a 64-bit quantity left or right by X bits, then the result is undefined by the language if X is a negative signed number or a positive number >= 64.

In practice, every compiler I've encountered for X86 platforms will treat it as a shift of X & 63 (or X & 31 if the left operand was a 32-bit quantity). I.e. they just generate a shr or shl instruction and the hardware only uses the bottom 5 or 6 bits of the register with the shift amount in it. Its better not to assume that, though: suppose that an optimizer could determine that your shift amount was always 64 or higher--it would be perfectly legitimate for it to optimize the shift expression out of existence and stick a constant zero in there instead.

That's the bug I had in Cyrano recently.
When the compiler generates a call the to run time library for the shift (like __allshl) the result is correct because the library will verify if count >= 64 and return zero.
But then when using another compiler there was no runtime library call but instead the instruction to do the shift - without the check on the count >= 64, the result was of course incorrect.

HJ.

wgarvin wrote:Not the best source, but anyways, from Microsoft's help:

"The results are undefined if the right operand of a shift expression is negative or if the right operand is greater than or equal to the number of bits in the (promoted) left operand."


In other words, if you shift a 64-bit quantity left or right by X bits, then the result is undefined by the language if X is a negative signed number or a positive number >= 64.

I read it but I did not care about that problem but about the problem when the shift cannot give you the mathematical value

"The value of a right-shift expression e1 >> e2 is e1 / 2e2, and the value of a left-shift expression e1 << e2 is e1 * 2e2."

e1*2e2 for e1=32 e2=33 is not a 64 bit number so I wanted to be sure that all value that are at least 2^64 become 0.

It is not clear from the explanation of microsoft and they do not give examples that demonstrate these cases.

Maybe I should know it from the definition of * but unforutnately I do not know what * means when the result is out of bounds and I do not know what is (1<<17)*(1<<17) when the computer use 32 bits numbers.
I am not sure if it is 0 or something else.

Uri

Uri Blass wrote:

wgarvin wrote:Not the best source, but anyways, from Microsoft's help:

"The results are undefined if the right operand of a shift expression is negative or if the right operand is greater than or equal to the number of bits in the (promoted) left operand."


In other words, if you shift a 64-bit quantity left or right by X bits, then the result is undefined by the language if X is a negative signed number or a positive number >= 64.

I read it but I did not care about that problem but about the problem when the shift cannot give you the mathematical value

"The value of a right-shift expression e1 >> e2 is e1 / 2e2, and the value of a left-shift expression e1 << e2 is e1 * 2e2."

e1*2e2 for e1=32 e2=33 is not a 64 bit number so I wanted to be sure that all value that are at least 2^64 become 0.

It is not clear from the explanation of microsoft and they do not give examples that demonstrate these cases.

Maybe I should know it from the definition of * but unforutnately I do not know what * means when the result is out of bounds and I do not know what is (1<<17)*(1<<17) when the computer use 32 bits numbers.
I am not sure if it is 0 or something else.

Uri

Shift just shifts left or right N bits. The result can be zero or non-zero depending on the original value being shifted. 2 << 63 is zero for example, as is 2 >>2.

The issue is in the shift count itself. Some machines (not the PC) would compute register >> N where N is >= 32 and give a zero value. Ditto for left-shift of 32 or more. Many machines just use a 5 or 6 bit counter depending on whether they are 32 or 64 bit processors, and ignore the extra bits to the left, so that shifting left 65 really just shifts left 1 bit.

Also note that shifting signed values violates the divide by two rule as the only exception, as -1 shifted right one bit is not zero on most hardware platforms, although a couple have done it right in the past... where in integer math -1 / 2 is zero.

bob wrote:Also note that shifting signed values violates the divide by two rule as the only exception, as -1 shifted right one bit is not zero on most hardware platforms, although a couple have done it right in the past... where in integer math -1 / 2 is zero.

This has been an amusing source of optimizer bugs in the past too. Strength-reduction of divisions of a signed number by a power of two into a shift instruction can give wrong results on negative numbers, but over the years there have been plenty of compilers that did it anyway. I don't know of any modern compilers that get this wrong though (yay).

These are the official rules from the ANSI/ISO C standard. If a compiler does not follow these rules it is broken and you can legitimately complain to your compiler vendor and if they claim ANSI or ISO compliance then they must fix it. From "ISO/IEC 9899:1999 (E)":

"6.5.7 Bitwise shift operators
Syntax
1 shift-expression:
additive-expression
shift-expression << additive-expression
shift-expression >> additive-expression
Constraints
2 Each of the operands shall have integer type.
Semantics
3 The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.
4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 * 2^(E2), reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 * 2^(E2) is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.
5 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 / 2^(E2). If E1 has a signed type and a negative value, the resulting value is implementation-defined."

Dann Corbit wrote: Semantics
3 The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

That seems pretty clear.

Dann Corbit wrote: 4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 * 2^(E2), reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 * 2^(E2) is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

Consistent with above, if E2 is greater than or equal to the number of bits in E1, the compiler can do whatever it wants because E1 * 2^(E2) is not "representable in the result type".

Dann Corbit wrote: 5 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 / 2^(E2). If E1 has a signed type and a negative value, the resulting value is implementation-defined."

I suspect the reason for this part, is that when the C language was invented there were some weird machines around that didn't use 2's-complement arithmetic. Every CPU made in the last 20 years or so uses 2's-complement arithmetic and so nearly every compiler does the same thing when you shift right a signed E1: it replicates the sign bit. But I guess the C standard still allows for the possibility of weird machines where negative numbers are represented in some other way and the compiler might want to do something...weird, instead.

wgarvin wrote:

Dann Corbit wrote: Semantics
3 The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

That seems pretty clear.

Dann Corbit wrote: 4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 * 2^(E2), reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 * 2^(E2) is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

Consistent with above, if E2 is greater than or equal to the number of bits in E1, the compiler can do whatever it wants because E1 * 2^(E2) is not "representable in the result type".

Dann Corbit wrote: 5 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 / 2^(E2). If E1 has a signed type and a negative value, the resulting value is implementation-defined."

I suspect the reason for this part, is that when the C language was invented there were some weird machines around that didn't use 2's-complement arithmetic. Every CPU made in the last 20 years or so uses 2's-complement arithmetic and so nearly every compiler does the same thing when you shift right a signed E1: it replicates the sign bit. But I guess the C standard still allows for the possibility of weird machines where negative numbers are represented in some other way and the compiler might want to do something...weird, instead.

Interestingly, in the C99 standard, there are some integral types for which 2's complement is mandatory. For example:

"7.18.1.1 Exact-width integer types
1 The typedef name intN_t designates a signed integer type with width N, no padding bits, and a two’s complement representation."