Przesunięcie bitowe i największa liczba całkowita w Bash

16

To pytanie dotyczące eksploracji, co oznacza, że ​​nie jestem całkowicie pewien, o co chodzi w tym pytaniu, ale myślę, że chodzi o największą liczbę całkowitą w Bash. W każdym razie zdefiniuję to pozornie.

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

Tworzę liczbę całkowitą, przesuwając nieco. Jak daleko mogę się posunąć?

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

Najwyraźniej nie tak daleko. (1 jest nieoczekiwany i wrócę do niego). Ale,

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

jest nadal pozytywny. Jednak nie to:

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

I krok dalej,

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

Dlaczego 1? A dlaczego następujące?

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

Czy ktoś chciałby przeanalizować tę serię?

AKTUALIZACJA

Moja maszyna:

$ 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- przestań być zły”
źródło
-9223372036854775808 = 0xF333333333333334. To zabawnie wyglądająca obudowa. Oczywiście 4611686018427387904 = 0x4000000000000000. Podejrzewam, że uderzasz w coś w rodzaju liczby bitów do przesunięcia. Dlaczego to robisz?
CVn
6
@ MichaelKjörling Dla rozrywki ;-p
2
@ MichaelKjörling Nie, nie jest. -9223372036854775808 to 0x8000000000000000. Podczas sprawdzania pominąłeś ostatnią cyfrę: -922337203685477580 to 0xF333333333333334.
hvd

Odpowiedzi:

27

Bash używa intmax_tzmiennych do arytmetyki . W twoim systemie mają one długość 64 bitów, więc:

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

który jest

100000000000000000000000000000000000000000000000000000000000000

binarnie (1, a następnie 62 0). Przesuń to jeszcze raz:

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

który jest

1000000000000000000000000000000000000000000000000000000000000000

binarnie (63 0s), w arytmetyki dopełniacza dwóch.

Aby uzyskać największą reprezentatywną liczbę całkowitą, musisz odjąć 1:

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

który jest

111111111111111111111111111111111111111111111111111111111111111

binarnie.

Jak wskazano w ilkkachu „s odpowiedzi , przenosząc zajmuje offset modulo 64 na 64-bitowych x86 procesorów (czy używając RCLlub SHL), który wyjaśnia zachowanie widzisz:

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

jest równoważne z $((1<<0)). Tak więc $((1<<1025))to $((1<<1)), $((1<<1026))jest $((1<<2))...

Znajdziesz definicje typów i maksymalne wartości w stdint.h; w twoim systemie:

/* 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
źródło
1
Nie, potrzebujesz ich, Binary -ma wyższy priorytet niż <<.
cuonglm
1
@cuonglm huh, służy mi do testowania na zsh ... Jeszcze raz dziękuję!
Stephen Kitt
@cuonglm and Stephen. To dobra edycja. echo $((1<<63-1))daje mi 4611686018427387904.
@tomas yup, bash używa pierwszeństwa operatora C, zsh ma domyślnie własne, gdzie $((1<<63-1))jest równe $(((1<<63)-1)).
Stephen Kitt
To dobrze wiedzieć, dobre pytanie i bardzo szczegółowa odpowiedź, dzięki wam zarówno Stephenowi Kittowi, jak i Tomkowi.
Valentin B.,
4

Z CHANGESpliku dla wersji bash2.05b:

jot. Powłoka wykonuje teraz arytmetykę w największym rozmiarze całkowitym obsługiwanym przez maszynę (intmax_t), zamiast w długim.

Na maszynach x86_64 intmax_todpowiada 64-bitowym liczbom całkowitym ze znakiem. Otrzymujesz znaczące wartości między -2^63i 2^63-1. Poza tym zakresem po prostu się owijasz.

Satō Katsura
źródło
Nitpick: między -2^63i 2^63-1włącznie.
Nominal Animal
4

Przesunięcie o 1024 daje jeden, ponieważ wielkość przesunięcia jest skutecznie brana modulo do liczby bitów (64), a więc 1024 === 64 === 0i 1025 === 65 === 1.

Przesunięcie czegoś innego niż a 1wyjaśnia, że ​​to nie jest mały obrót, ponieważ wyższe bity nie zawijają się do dolnego końca, zanim wartość przesunięcia wynosi (przynajmniej) 64:

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

Możliwe, że takie zachowanie zależy od systemu. Kod bash Stephen związana pokazuje tylko zwykły przesunięcie, bez jakiejkolwiek kontroli dla wartości po prawej stronie. Jeśli dobrze pamiętam, procesory x86 używają tylko dolnych sześciu bitów wartości przesunięcia (w trybie 64-bitowym), więc zachowanie może być bezpośrednio z języka maszynowego. Ponadto myślę, że przesunięcia o więcej niż szerokość bitów również nie są jasno określone w C ( gccostrzega przed tym).

ilkkachu
źródło
2

generując liczbę całkowitą przez nieznaczne przesunięcie. Jak daleko mogę się posunąć?

Dopóki nie zapełni się reprezentacja liczb całkowitych (domyślna w większości powłok).
64-bitowa liczba całkowita zwykle otacza 2**63 - 1.
To 0x7ffffffffffffffflub 9223372036854775807w grudniu.

Ta liczba „+1” staje się ujemna.

To jest tak samo, jak 1<<63:

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

Następnie proces powtarza się ponownie.

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

Wynik zależy mod 64od wartości przesunięcia [a] .

[a] From: Intel® 64 and IA-32 Architectures Software Developer's Manual: Tom 2 Liczba jest maskowana do 5 bitów (lub 6 bitów, jeśli jest w trybie 64-bitowym i używany jest REX.W). Zakres zliczania jest ograniczony od 0 do 31 (lub 63, jeśli używany jest tryb 64-bitowy i REX.W). .

Pamiętaj też, że $((1<<0))tak1

$ 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

Wszystko zależy więc od tego, jak blisko jest liczba do wielokrotności 64.

Testowanie limitu:

Solidnym sposobem na sprawdzenie, która jest maksymalną dodatnią (i ujemną) liczbą całkowitą, jest przetestowanie każdego bitu po kolei. W każdym razie jest to mniej niż 64 kroki dla większości komputerów, nie będzie to zbyt wolne.

grzmotnąć

Najpierw potrzebujemy największej liczby całkowitej w formularzu 2^n(zestaw 1 bitów, po których następują zera). Możemy to zrobić, przesuwając w lewo, aż następna zmiana spowoduje, że liczba będzie ujemna, zwana również „zawijaniem”:

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

Gdzie bjest wynik: wartość przed ostatnim przesunięciem, które zawiedzie pętlę.

Następnie musimy co najmniej starać się dowiedzieć, które z nich wpływają na znak e:

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

Maksymalna liczba całkowita ( intmax) wynika z ostatniej wartości d.

Z drugiej strony (mniej niż 0) powtarzamy wszystkie testy, ale testujemy, kiedy bit można zrobić 0 bez zawijania.

Cały test z wydrukowaniem wszystkich kroków jest następujący (dla 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

Przetłumaczone na prawie każdą powłokę:

#!/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"

Uruchamiając powyższe dla wielu powłok,
wszystkie (oprócz bash 2.04 i mksh) zaakceptowały wartości do ( 2**63 -1) na tym komputerze.

Interesujące jest zgłoszenie, że powłoka att :

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

wypisał błąd na wartościach $((2^63)), a nie ksh.

sorontar
źródło