Cambio bit a bit y el entero más grande en Bash

16

Esta es una pregunta de exploración, lo que significa que no estoy completamente seguro de qué se trata esta pregunta, pero creo que se trata del mayor número entero en Bash. De todos modos, lo definiré con ostentación.

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

Estoy produciendo un número entero cambiando un poco. ¿Hasta dónde puedo llegar?

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

No tan lejos, al parecer. (1 es inesperado, y volveré sobre ello.) Pero,

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

Sigue siendo positivo. No esto, sin embargo:

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

Y un paso más allá,

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

¿Por qué 1? ¿Y por qué lo siguiente?

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

¿A alguien le gustaría analizar esta serie?

ACTUALIZAR

Mi maquina:

$ 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
Gilles 'SO- deja de ser malvado'
fuente
-9223372036854775808 = 0xF333333333333334. Ese es un caso de borde de aspecto gracioso. Por supuesto, 4611686018427387904 = 0x4000000000000000. Sospecho que está llegando a algún tipo de cambio en la cantidad de bits por los que debe cambiar. ¿Por qué haces esto, de todos modos?
un CVn
66
@ MichaelKjörling Para diversión ;-p
2
@ MichaelKjörling No, no lo es. -9223372036854775808 sería 0x8000000000000000. Omitió el último dígito al marcar: -922337203685477580 sería 0xF333333333333334.
hvd

Respuestas:

27

Bash usa intmax_tvariables para la aritmética . En su sistema, estos tienen 64 bits de longitud, así que:

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

cual es

100000000000000000000000000000000000000000000000000000000000000

en binario (1 seguido de 62 0s). Cambia eso de nuevo:

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

cual es

1000000000000000000000000000000000000000000000000000000000000000

en binario (63 0s), en aritmética del complemento a dos.

Para obtener el mayor entero representable, debe restar 1:

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

cual es

111111111111111111111111111111111111111111111111111111111111111

en binario

Como se señaló en la respuesta de ilkkachu , el cambio toma el módulo de compensación 64 en CPU x86 de 64 bits (ya sea que use o ), lo que explica el comportamiento que está viendo:RCLSHL

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

es equivalente a $((1<<0)). Así $((1<<1025))es $((1<<1)), $((1<<1026))es $((1<<2))...

Encontrará las definiciones de tipo y los valores máximos en stdint.h; en su sistema:

/* 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))
Stephen Kitt
fuente
1
No, los necesitas, Binary -tiene mayor prioridad que <<.
Cuonglm
1
@cuonglm eh, me sirve para probar en zsh ... ¡Gracias de nuevo!
Stephen Kitt
@cuonglm y Stephen. Bueno, esa es una buena edición. echo $((1<<63-1))me da 4611686018427387904.
@tomas sí, bash usa la precedencia del operador C, zsh tiene el suyo por defecto donde $((1<<63-1))es igual $(((1<<63)-1)).
Stephen Kitt
Es bueno saberlo, una buena pregunta y una respuesta muy exhaustiva, gracias a ambos Stephen Kitt y Tomas.
Valentin B.
4

Del CHANGESarchivo para bash2.05b:

j. El shell ahora realiza aritmética en el tamaño entero más grande que admite la máquina (intmax_t), en lugar de largo.

En máquinas x86_64 intmax_tcorresponde a enteros de 64 bits con signo. Entonces obtienes valores significativos entre -2^63y 2^63-1. Fuera de ese rango, solo obtienes envolturas.

Satō Katsura
fuente
Nitpick: entre -2^63y 2^63-1, inclusive.
Nominal Animal
4

El desplazamiento por 1024 da un uno, porque la cantidad de desplazamiento se toma efectivamente módulo el número de bits (64), entonces 1024 === 64 === 0, y 1025 === 65 === 1.

Al cambiar algo distinto de a, 1queda claro que no es una rotación de bits, ya que los bits más altos no se ajustan al extremo inferior antes de que el valor de desplazamiento sea (al menos) 64:

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

Puede ser que este comportamiento dependa del sistema. El código de bash con el que se vinculó Stephen muestra solo un cambio simple, sin verificar el valor de la mano derecha. Si no recuerdo mal, los procesadores x86 solo usan los seis bits inferiores del valor de desplazamiento (en modo de 64 bits), por lo que el comportamiento puede ser directamente del lenguaje de la máquina. Además, creo que los cambios en más del ancho de bits tampoco están claramente definidos en C ( gccadvierte eso).

ilkkachu
fuente
2

produciendo un número entero cambiando un poco. ¿Hasta dónde puedo llegar?

Hasta que la representación entera se envuelva (el valor predeterminado en la mayoría de los shells).
Un entero de 64 bits generalmente se envuelve en 2**63 - 1.
Eso es 0x7fffffffffffffffo 9223372036854775807en diciembre.

Ese número '+1' se vuelve negativo.

Eso es lo mismo que 1<<63, por lo tanto:

$ echo "$((1<<62)) $((1<<63)) and $((1<<64))"
4611686018427387904 -9223372036854775808 and 1

Después de eso, el proceso se repite nuevamente.

$((1<<80000)) $((1<<1022)) $((1<<1023)) $((1<<1024)) $((1<<1025)) $((1<<1026))

El resultado depende mod 64del valor de desplazamiento [a] .

[a] De: Intel® 64 e IA-32 Architectures Software Developer's Manual: Volumen 2 El recuento se enmascara a 5 bits (o 6 bits si está en modo de 64 bits y se utiliza REX.W). El rango de conteo está limitado de 0 a 31 (o 63 si se usa el modo de 64 bits y REX.W). .

Además: recuerda que $((1<<0))es1

$ for i in 80000 1022 1023 1024 1025 1026; do echo "$((i%64)) $((1<<i))"; done
 0 1
62 4611686018427387904
63 -9223372036854775808
 0 1
 1 2
 2 4

Entonces, todo depende de qué tan cerca esté el número a un múltiplo de 64.

Probar el límite:

La forma sólida de probar cuál es el número entero positivo (y negativo) máximo es probar cada bit por turno. De todos modos, tiene menos de 64 pasos para la mayoría de las computadoras, no será demasiado lento.

golpetazo

Primero necesitamos el mayor número entero de la forma 2^n(conjunto de 1 bit seguido de ceros). Podemos hacerlo desplazándonos hacia la izquierda hasta que el próximo desplazamiento haga que el número sea negativo, también llamado "ajuste"

a=1;   while ((a>0));  do ((b=a,a<<=1))  ; done

Dónde bestá el resultado: el valor antes del último turno que falla el ciclo.

Luego, debemos intentar cada poco para descubrir cuáles afectan el signo de e:

c=$b;d=$b;
while ((c>>=1)); do
      ((e=d+c))
      (( e>0 )) && ((d=e))
done;
intmax=$d

El número entero máximo ( intmax) resulta del último valor de d.

En el lado negativo (menos de 0), repetimos todas las pruebas, pero comprobamos cuándo se puede hacer un bit 0 sin ajustar.

Una prueba completa con la impresión de todos los pasos es la siguiente (para bash):

#!/bin/bash
sayit(){ printf '%020d 0x%016x\n' "$1"{,}; }
a=1;       while ((a>0)) ; do((b=a,a<<=1))              ; sayit "$a"; done
c=$b;d=$b; while((c>>=1)); do((e=d+c));((e>0))&&((d=e)) ; sayit "$d"; done;
intmax=$d
a=-1;      while ((a<0)) ; do((b=a,a<<=1))              ; sayit "$b"; done;
c=$b;d=$b; while ((c<-1)); do((c>>=1,e=d+c));((e<0))&&((d=e)); sayit "$d"; done
intmin=$d       

printf '%20d max positive value 0x%016x\n' "$intmax" "$intmax"
printf '%20d min negative value 0x%016x\n' "$intmin" "$intmin"

sh

Traducido a casi cualquier shell:

#!/bin/sh
printing=false
sayit(){ "$printing" && printf '%020d 0x%016x\n' "$1" "$1"; }
a=1;       while [ "$a" -gt 0  ];do b=$a;a=$((a<<1)); sayit "$a"; done
c=$b;d=$b; while c=$((c>>1)); [ "$c" -gt 0 ];do e=$((d+c)); [ "$e" -gt 0 ] && d=$e ; sayit "$d"; done;
intmax=$d
a=-1;      while [ "$a" -lt 0  ];do b=$a;a=$((a<<1)); sayit "$b"; done;
c=$b;d=$b; while [ "$c" -lt -1 ];do c=$((c>>1));e=$((d+c));[ "$e" -lt 0 ] && d=$e ; sayit "$d"; done
intmin=$d       

printf '%20d max positive value 0x%016x\n' "$intmax" "$intmax"
printf '%20d min negative value 0x%016x\n' "$intmin" "$intmin"

Al ejecutar lo anterior para muchos shells,
todos (excepto bash 2.04 y mksh) aceptaron valores hasta ( 2**63 -1) en esta computadora.

Es interesante informar que el shell att :

$ attsh --version
version         sh (AT&T Research) 93u+ 2012-08-01

imprimió un error en los valores de $((2^63)), no ksh sin embargo.

sorontar
fuente