Bitwise shift and the largest integer in Bash

Bash uses intmax_t variables for arithmetic. On your system these are 64 bits in length, so:

$ echo $((1<<62))
4611686018427387904

which is

100000000000000000000000000000000000000000000000000000000000000

in binary (1 followed by 62 0s). Shift that again:

$ echo $((1<<63))
-9223372036854775808

which is

1000000000000000000000000000000000000000000000000000000000000000

in binary (63 0s), in two's complement arithmetic.

To get the biggest representable integer, you need to subtract 1:

$ echo $(((1<<63)-1))
9223372036854775807

which is

111111111111111111111111111111111111111111111111111111111111111

in binary.

As pointed out in ilkkachu's answer, shifting takes the offset modulo 64 on 64-bit x86 CPUs (whether using RCL or SHL), which explains the behaviour you're seeing:

$ echo $((1<<64))
1

is equivalent to $((1<<0)). Thus $((1<<1025)) is $((1<<1)), $((1<<1026)) is $((1<<2))...

You'll find the type definitions and maximum values in stdint.h; on your system:

/* Largest integral types.  */
#if __WORDSIZE == 64
typedef long int                intmax_t;
typedef unsigned long int       uintmax_t;
#else
__extension__
typedef long long int           intmax_t;
__extension__
typedef unsigned long long int  uintmax_t;
#endif

/* Minimum for largest signed integral type.  */
# define INTMAX_MIN             (-__INT64_C(9223372036854775807)-1)
/* Maximum for largest signed integral type.  */
# define INTMAX_MAX             (__INT64_C(9223372036854775807))

From the CHANGES file for bash 2.05b:

j. The shell now performs arithmetic in the largest integer size the machine supports (intmax_t), instead of long.

On x86_64 machines intmax_t corresponds to signed 64-bits integers. So you get meaningful values between -2^63 and 2^63-1. Outside that range you just get wrap-arounds.

Shifting by 1024 gives a one, because the shift amount is effectively taken modulo the number of bits (64), so 1024 === 64 === 0, and 1025 === 65 === 1.

Shifting something other than a 1 makes it clear it's not a bit rotation, as the higher bits don't wrap around to the low end before the shift value is (at least) 64:

$ printf "%x\n" $(( 5 << 63 )) $(( 5 << 64 ))
8000000000000000
5

It may be that this behaviour depends on the system. The bash code Stephen linked to shows just a plain shift, without any checking for the right hand value. If I remember correctly, x86 processors only use the bottom six bits of the shift value (in 64-bit mode), so the behaviour may be directly from the machine language. Also, I think shifts by more than the bit width aren't clearly defined in C either (gcc warns for that).