Why Is 1>>32 == 1

why is 132 == 1?

http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.22.1

15.19 Shift Operators

If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x1f. The shift distance actually used is therefore always in the range 0 to 31, inclusive.

If the promoted type of the left-hand operand is long, then only the six lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x3f. The shift distance actually used is therefore always in the range 0 to 63, inclusive.

(emphasis mine)

Why is (-1 32) = -1?

The Java specification explains the shift operators as follows:

If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x1f. The shift distance actually used is therefore always in the range 0 to 31, inclusive.

The value of 32 & 0x1f is zero.

If the left operand is long, then you get an extra bit for the right operand, expanding the upper limit to 63 instead of 31.

In order to have any specific expected value from shifting -1 to the right, you need to specify the underlying binary representation of integers (e.g., two's complement) as well as the number of bits (e.g., 32). Each programming language can define those differently, but in the interest of keeping things simpler for the implementation, they'll usually specify that shifting by more than the number of available bits is not allowed. That's often because the underlying CPU hardware doesn't support it, either. After all, if you want to shift that many bits, the left operand no longer matters since the result will always be the same.

Why doesn't left bit-shift, , for 32-bit integers work as expected when used more than 32 times?

This is caused due to a combination of an undefined behaviour in C and the fact that code generated for IA-32 processors has a 5 bit mask applied on the shift count. This means that on IA-32 processors, the range of a shift count is 0-31 only. ¹

From The C programming language ²

The result is undefined if the right operand is negative, or greater than or equal to the number of bits in the left expression’s type.

From IA-32 Intel Architecture Software Developer’s Manual ³

The 8086 does not mask the shift count. However, all other IA-32 processors (starting with the Intel 286 processor) do mask the shift count to 5 bits, resulting in a maximum count of 31. This masking is done in all operating modes (including the virtual-8086 mode) to reduce the maximum execution time of the instructions.

¹ http://codeyarns.com/2004/12/20/c-shift-operator-mayhem/

² A7.8 Shift Operators, Appendix A. Reference Manual, The C Programming Language

³ SAL/SAR/SHL/SHR – Shift, Chapter 4. Instruction Set Reference, IA-32 Intel Architecture Software Developer’s Manual

Why does (1 31) 31 result in -1?

int z = 1;
z <<= 31;

Assuming int is 32 bit and two's complement representation is used, the left shift is undefined behavior in C because the result if not representable in the int type. From the standard:

The result of E1 << E2 is E1 left-shifted E2 bit positions

...

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.

In practice, it is likely to result in 0x80000000, which is treated as a negative number.

And right-shifting of negative integers is implementation-defined behavior:

The result of E1 >> E2 is E1 right-shifted E2 bit positions.

...

If E1 has a signed type and a negative value, the resulting value is implementation-defined.

In C++ left shift is defined in a similar way till C++14, as @T.C. mentioned (or, with some restrictions, might be even till C++11, as @MattMcNabb wrote).

But even if left-shift is defined and 0x8000000 is the expected value, the result of a right shift of a negative number is still implementation-defined.

right left shift bits in C

Right shifting an integer by a number of bits equal or greater than its size is undefined behavior.

C11 6.5.7 Bitwise shift operators

Syntax
shift-expression: additive-expression
    shift-expression << additive-expression
    shift-expression >> additive-expression
Constraints

Each of the operands shall have integer type.

Semantics

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.

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.

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.

The size of int on your platform seems to be at most 32 bits, so the initializers for bit32R and bit32L have undefined behavior.

The 64-bit expressions should be written:

uint64_t bit32R = (uint64_t)code >> 32;

and

uint64_t bit32L = (uint64_t)code << 32;

Furthermore, the formats used in printf are not correct for the arguments passed (unless int has 64 bits, which would produce different output).

Your compiler does not seem to be fully C99 compliant, you should add a final return 0; statement at the end of the body of function main().

Here is a corrected version:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <inttypes.h>

int main(void) {
    uint32_t code = 0xCDBAFFEE;

    uint64_t bit32R = (uint64_t)code >> 32;
    uint16_t bit16R = code >> 16;
    uint8_t bit8R = code >> 8;
    uint8_t bit0R = code >> 0;

    uint64_t bit32L = (uint64_t)code << 32;
    uint16_t bit16L = code << 16;
    uint8_t bit8L = code << 8;
    uint8_t bit0L = code << 0;

    printf("Right shift:\n"
           "bit32R %.16"PRIx64"\n"
           "bit16R %"PRIx16"\n"
           "bit8R %"PRIx8"\n"
           "bit0R %"PRIx8"\n\n",
           bit32R, bit16R, bit8R, bit0R);

    printf("Left shift:\n"
           "bit32L %.16"PRIx64"\n"
           "bit16L %"PRIx16"\n"
           "bit8L %"PRIx8"\n"
           "bit0L %"PRIx8"\n\n",
           bit32L, bit16L, bit8L, bit0L);

    return 0;
}

The output is:

Right shift:
bit32R 0000000000000000
bit16R cdba
bit8R ff
bit0R ee

Left shift:
bit32L cdbaffee00000000
bit16L 0
bit8L 0
bit0L ee

this might not be what you expect, because the types of the variables are somewhat inconsistent.

What are bitwise shift (bit-shift) operators and how do they work?

The bit shifting operators do exactly what their name implies. They shift bits. Here's a brief (or not-so-brief) introduction to the different shift operators.

The Operators

>> is the arithmetic (or signed) right shift operator.
>>> is the logical (or unsigned) right shift operator.
<< is the left shift operator, and meets the needs of both logical and arithmetic shifts.

All of these operators can be applied to integer values (int, long, possibly short and byte or char). In some languages, applying the shift operators to any datatype smaller than int automatically resizes the operand to be an int.

Note that <<< is not an operator, because it would be redundant.

Also note that C and C++ do not distinguish between the right shift operators. They provide only the >> operator, and the right-shifting behavior is implementation defined for signed types. The rest of the answer uses the C# / Java operators.

(In all mainstream C and C++ implementations including GCC and Clang/LLVM, >> on signed types is arithmetic. Some code assumes this, but it isn't something the standard guarantees. It's not undefined, though; the standard requires implementations to define it one way or another. However, left shifts of negative signed numbers is undefined behaviour (signed integer overflow). So unless you need arithmetic right shift, it's usually a good idea to do your bit-shifting with unsigned types.)

Left shift (<<)

Integers are stored, in memory, as a series of bits. For example, the number 6 stored as a 32-bit int would be:

00000000 00000000 00000000 00000110

Shifting this bit pattern to the left one position (6 << 1) would result in the number 12:

00000000 00000000 00000000 00001100

As you can see, the digits have shifted to the left by one position, and the last digit on the right is filled with a zero. You might also note that shifting left is equivalent to multiplication by powers of 2. So 6 << 1 is equivalent to 6 * 2, and 6 << 3 is equivalent to 6 * 8. A good optimizing compiler will replace multiplications with shifts when possible.

Non-circular shifting

Please note that these are not circular shifts. Shifting this value to the left by one position (3,758,096,384 << 1):

11100000 00000000 00000000 00000000

results in 3,221,225,472:

11000000 00000000 00000000 00000000

The digit that gets shifted "off the end" is lost. It does not wrap around.

Logical right shift (>>>)

A logical right shift is the converse to the left shift. Rather than moving bits to the left, they simply move to the right. For example, shifting the number 12:

00000000 00000000 00000000 00001100

to the right by one position (12 >>> 1) will get back our original 6:

00000000 00000000 00000000 00000110

So we see that shifting to the right is equivalent to division by powers of 2.

Lost bits are gone

However, a shift cannot reclaim "lost" bits. For example, if we shift this pattern:

00111000 00000000 00000000 00000110

to the left 4 positions (939,524,102 << 4), we get 2,147,483,744:

10000000 00000000 00000000 01100000

and then shifting back ((939,524,102 << 4) >>> 4) we get 134,217,734:

00001000 00000000 00000000 00000110

We cannot get back our original value once we have lost bits.

Arithmetic right shift (>>)

The arithmetic right shift is exactly like the logical right shift, except instead of padding with zero, it pads with the most significant bit. This is because the most significant bit is the sign bit, or the bit that distinguishes positive and negative numbers. By padding with the most significant bit, the arithmetic right shift is sign-preserving.

For example, if we interpret this bit pattern as a negative number:

10000000 00000000 00000000 01100000

we have the number -2,147,483,552. Shifting this to the right 4 positions with the arithmetic shift (-2,147,483,552 >> 4) would give us:

11111000 00000000 00000000 00000110

or the number -134,217,722.

So we see that we have preserved the sign of our negative numbers by using the arithmetic right shift, rather than the logical right shift. And once again, we see that we are performing division by powers of 2.

Explaining method (x n) | (x (32 - n))

A bitwise rotate operation shifts bits to the left, but also "rescues" bits shifted off the high end of the value and shifts them onto the low end. The | operation in that function combines the "lost" bits from the high end of the word — shifted down to the low end — with the remaining bits shifted up.

The shift upwards leaves 0 bits in the low end, so it's assured that the only 1 bits will be those that were set in the high end of the word before the rotation.

Bitwise (Bitshift) operations on 64-bit integers in C++

You need to use 1LL as 64 bit value before you use shift operator << to get 64 bit result:

#include <stdint.h>
uint64_t kings = 0ULL; 
kings |= 1ULL << i;