Bash – Bitwise Shift and the Largest Integer

arithmeticbash

This is an exploration question, meaning I'm not completely sure what this question is about, but I think it's about the biggest integer in Bash. Anyhow, I'll define it ostensively.

$ echo $((1<<8))
256

I'm producing an integer by shifting a bit. How far can I go?

$ echo $((1<<80000))
1

Not this far, apparently. (1 is unexpected, and I'll return to it.) But,

$ echo $((1<<1022))
4611686018427387904

is still positive. Not this, however:

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

And one step further afield,

$ echo $((1<<1024))
1

Why 1? And why the following?

$ echo $((1<<1025))
2
$ echo $((1<<1026))
4

Would someone like to analyse this series?

UPDATE

My machine:

$ uname -a
Linux tomas-Latitude-E4200 4.4.0-47-generic #68-Ubuntu SMP Wed Oct 26 19:39:52 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux

Best Answer

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))

Related Solutions

Bash: integer expression expected, using read/test

Actually you can set some attributes on variables using the declare (or the old typeset) builtin. declare -i var1 var2 will set integer attribute on those variables. After that assignments which attempt to set non-integer values to those variables will raise error.

But your problem is with the syntax. When using a variable's value you have to prefix its name with $:

if [ "$var1" -lt "$var2" ]; then
    echo "$var1 is lt $var2"
else
    echo "$var2 is lt $var1"
fi

Exceptions are the arithmetic evaluations, where is no need for the $:

if ((var1<var2)); then
    echo "$var1 is lt $var2"
else
    echo "$var2 is lt $var1"
fi

As a word of warning, inside [..] always double quote your variables to avoid word expansion messing up your expression's syntax. (I mean, you will have problems with unset variables, variables containing empty string and variables containing IFS characters.) Or you can use the newer and better [[..]] instead which handles such cases correctly:

if [[ $var1 -lt $var2 ]]; then
    echo "$var1 is lt $var2"
else
    echo "$var2 is lt $var1"
fi

Bash – How to iterate a zero padded integer in bash

In bash, numbers with leading zeros are considered as octal. To force bash to consider them as decimal, you can add a 10# prefix:

next_number=$(printf %06d "$((10#$current_number + 1))")

Or with bash 3.1 or above, to avoid the forking:

printf -v next_number %06d "$((10#$current_number + 1))"

(note that it doesn't work for negative numbers as 10#-010 is seen as 10#0 - 010 in bash, so both $((10#-10)) and $((-10#-10)) expand to -8).

Best Answer

Related Solutions

Bash: integer expression expected, using read/test

Bash – How to iterate a zero padded integer in bash

Related Question