Mudança bit a bit e o maior número inteiro no Bash

16

Esta é uma questão de exploração, o que significa que não tenho certeza do que se trata, mas acho que é o maior número inteiro no Bash. De qualquer forma, vou defini-lo ostensivamente.

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

Estou produzindo um número inteiro deslocando um pouco. Até onde posso ir?

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

Não tão longe, aparentemente. (1 é inesperado e voltarei a ele.) Mas,

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

ainda é positivo. Não é isso, no entanto:

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

E um passo adiante,

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

Por que 1? E por que o seguinte?

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

Alguém gostaria de analisar esta série?

ATUALIZAR

Minha máquina:

$ 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- parar de ser mau'
fonte
-9223372036854775808 = 0xF333333333333334. Esse é um caso estranho. Obviamente, 4611686018427387904 = 0x4000000000000000000. Eu suspeito que você está acertando algum tipo de explicação sobre o número de bits a serem trocados. Por que você está fazendo isso, afinal?
um CVn
6
@ MichaelKjörling For
2
@ MichaelKjörling Não, não é. -9223372036854775808 seria 0x8000000000000000. Você deixou o dígito final ao marcar: -922337203685477580 seria 0xF333333333333334.
hvd 23/11

Respostas:

27

O Bash usa intmax_tvariáveis ​​para aritmética . No seu sistema, eles têm 64 bits de comprimento, portanto:

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

qual é

100000000000000000000000000000000000000000000000000000000000000

em binário (1 seguido por 62 0s). Mude isso novamente:

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

qual é

1000000000000000000000000000000000000000000000000000000000000000

em binário (63 0s), na aritmética do complemento de dois.

Para obter o maior número inteiro representável, você precisa subtrair 1:

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

qual é

111111111111111111111111111111111111111111111111111111111111111

em binário.

Como fora apontado em ilkkachu 's resposta , mudando leva o deslocamento módulo 64 em 64-bit x86 CPUs (seja usando RCLou SHL), o que explica o comportamento que você está vendo:

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

é equivalente a $((1<<0)). Assim $((1<<1025))é $((1<<1)), $((1<<1026))é $((1<<2))...

Você encontrará as definições de tipo e os valores máximos em stdint.h; no seu 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
fonte
1
Não, você precisa deles, o binário -tem maior precedência do que <<.
cuonglm
1
@cuonglm hein, serve-me bem para testar no zsh ... Mais uma vez obrigado!
Stephen Kitt
@cuonglm e Stephen. Bem, essa é uma boa edição. echo $((1<<63-1))me dá 4611686018427387904.
@tomas yup, o bash usa a precedência do operador C, o zsh tem seu próprio padrão por padrão, onde $((1<<63-1))é igual a $(((1<<63)-1)).
Stephen Kitt
É bom saber, uma boa pergunta e uma resposta muito completa, graças a você, Stephen Kitt e Tomas.
Valentin B.
4

Do CHANGESarquivo para bash2.05b:

j. O shell agora executa aritmética no maior tamanho inteiro suportado pela máquina (intmax_t), em vez de longo.

Em máquinas x86_64 intmax_tcorresponde a números inteiros de 64 bits assinados. Então você obtém valores significativos entre -2^63e 2^63-1. Fora desse intervalo, você apenas recebe envolvimentos.

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

Mudar para 1024 fornece um, porque a quantidade de deslocamento é efetivamente tomada modulando o número de bits (64), então 1024 === 64 === 0, e 1025 === 65 === 1.

Mudar algo diferente de a 1deixa claro que não é uma rotação de bits, já que os bits mais altos não se aproximam da extremidade inferior antes que o valor da mudança seja (pelo menos) 64:

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

Pode ser que esse comportamento dependa do sistema. O código do bash ao qual Stephen se vinculou mostra apenas uma mudança simples, sem qualquer verificação do valor à direita. Se bem me lembro, os processadores x86 usam apenas os seis bits inferiores do valor de deslocamento (no modo de 64 bits); portanto, o comportamento pode ser diretamente da linguagem da máquina. Além disso, acho que as mudanças além da largura do bit também não estão claramente definidas em C ( gccalerta para isso).

ilkkachu
fonte
2

produzindo um número inteiro deslocando um pouco. Até onde posso ir?

Até que a representação inteira envolva (o padrão na maioria dos shells).
Um número inteiro de 64 bits geralmente envolve em 2**63 - 1.
Isso é 0x7fffffffffffffffou 9223372036854775807em dezembro.

Esse número '+1' se torna negativo.

É o mesmo que 1<<63, assim:

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

Depois disso, o processo se repete novamente.

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

O resultado depende mod 64do valor de mudança [a] .

[a] De: Manual do desenvolvedor de software das arquiteturas Intel® 64 e IA-32: Volume 2 A contagem é mascarada em 5 bits (ou 6 bits se estiver no modo de 64 bits e REX.W estiver sendo usado). O intervalo de contagem é limitado de 0 a 31 (ou 63 se o modo de 64 bits e o REX.W forem usados). .

Lembre-se também de que $((1<<0))é1

$ 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

Portanto, tudo depende da proximidade do número de um múltiplo de 64.

Testando o limite:

A maneira robusta de testar qual é o número máximo positivo (e negativo) máximo é testar cada um por vez. Seus menos de 64 passos para a maioria dos computadores, de qualquer maneira, não será muito lento.

bater

Primeiro, precisamos do maior número inteiro do formulário 2^n(conjunto de 1 bit seguido por zeros). Podemos fazer isso deslocando a esquerda até o próximo turno tornar o número negativo, também chamado de "contornar":

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

Onde bestá o resultado: o valor antes do último turno que falha no loop.

Então, precisamos tentar todos os detalhes para descobrir quais afetam o sinal de e:

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

O número inteiro máximo ( intmax) resulta do último valor de d.

No lado negativo (menos que 0), repetimos todos os testes, mas testamos quando um pouco pode ser feito 0 sem envolver.

Um teste completo com a impressão de todas as etapas é este (para o 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

Traduzido para quase qualquer 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"

Executando o descrito acima para muitos shells,
todos (exceto o bash 2.04 e o mksh) aceitaram valores de até ( 2**63 -1) neste computador.

É interessante relatar que o shell att :

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

imprimiu um erro nos valores de $((2^63)), mas não no ksh.

sorontar
fonte