Bitweise Verschiebung und die größte Ganzzahl in Bash

16

Dies ist eine Erkundungsfrage, was bedeutet, dass ich nicht ganz sicher bin, worum es bei dieser Frage geht, aber ich denke, es geht um die größte Ganzzahl in Bash. Wie auch immer, ich werde es scheinbar definieren.

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

Ich produziere eine ganze Zahl, indem ich ein bisschen verschiebe. Wie weit kann ich gehen?

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

Offenbar nicht so weit. (1 ist unerwartet, und ich werde darauf zurückkommen.) Aber,

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

ist immer noch positiv. Nicht dies jedoch:

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

Und noch einen Schritt weiter,

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

Warum 1? Und warum das Folgende?

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

Möchte jemand diese Serie analysieren?

AKTUALISIEREN

Meine Maschine:

$ 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
Tomasz
quelle
-9223372036854775808 = 0xF333333333333334. Das ist ein komisch aussehender Randfall. Natürlich 4611686018427387904 = 0x4000000000000000. Ich vermute, dass Sie die Anzahl der Bits, um die verschoben werden soll, in irgendeiner Weise umgehen. Warum machst du das überhaupt?
ein Lebenslauf vom
6
@ MichaelKjörling Zur Unterhaltung ;-p
Tomasz
2
@ MichaelKjörling Nein, ist es nicht. -9223372036854775808 wäre 0x8000000000000000. Sie haben die letzte Ziffer bei der Überprüfung ausgelassen: -922337203685477580 wäre 0xF333333333333334.
HDV

Antworten:

27

Bash verwendet intmax_tVariablen für die Arithmetik . Auf Ihrem System sind diese 64 Bit lang, also:

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

welches ist

100000000000000000000000000000000000000000000000000000000000000

binär (1 gefolgt von 62 0s). Verschiebe das nochmal:

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

welches ist

1000000000000000000000000000000000000000000000000000000000000000

in binärer (63 0s), in Zweierkomplementarithmetik.

Um die größte darstellbare Ganzzahl zu erhalten, müssen Sie 1 subtrahieren:

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

welches ist

111111111111111111111111111111111111111111111111111111111111111

in binär.

Wie in der Antwort von ilkkachu ausgeführt , wird für das Verschieben das Offsetmodul 64 auf 64-Bit- x86- CPUs (unabhängig davon, ob verwendet oder ) verwendet. Dies erklärt das Verhalten, das Sie sehen:RCLSHL

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

ist äquivalent zu $((1<<0)). Also $((1<<1025))ist $((1<<1)), $((1<<1026))ist $((1<<2))...

Die Typdefinitionen und Maximalwerte finden Sie in stdint.h; auf Ihrem 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))
Stephen Kitt
quelle
1
Nein, du brauchst sie. Binär -hat höhere Priorität als <<.
Donnerstag,
1
@cuonglm huh, dient mir gleich zum testen auf zsh ... Danke nochmal!
Stephen Kitt
@ Cuonglm und Stephen. Nun, das ist eine gute Bearbeitung. echo $((1<<63-1))gibt mir 4611686018427387904.
Tomasz
@tomas yup, bash verwendet C-Operator-Priorität, zsh hat standardmäßig eine eigene, wobei $((1<<63-1))gleich ist $(((1<<63)-1)).
Stephen Kitt
Das ist gut zu wissen, eine gute Frage und eine sehr gründliche Antwort, danke an Sie beide, Stephen Kitt und tomas.
Valentin B.
4

Aus der CHANGESDatei für bash2.05b:

j. Die Shell führt nun eine Arithmetik mit der größten von der Maschine unterstützten Ganzzahlgröße (intmax_t) anstelle von long durch.

Auf x86_64-Computern intmax_tentspricht dies vorzeichenbehafteten 64-Bit-Ganzzahlen. So erhalten Sie aussagekräftige Werte zwischen -2^63und 2^63-1. Außerhalb dieses Bereichs erhalten Sie nur Umwicklungen.

Satō Katsura
quelle
Nitpick: zwischen -2^63und 2^63-1, inklusive.
Nominale Tier
4

Eine Verschiebung um 1024 ergibt eine Eins, da der Verschiebungsbetrag effektiv modulo der Anzahl von Bits (64) genommen wird, also 1024 === 64 === 0und 1025 === 65 === 1.

Wenn Sie etwas anderes als a verschieben, 1wird deutlich, dass es sich nicht um eine Bit-Rotation handelt, da die höheren Bits nicht auf das untere Ende umlaufen, bevor der Verschiebungswert (mindestens) 64 beträgt:

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

Es kann sein, dass dieses Verhalten vom System abhängt. Der Bash-Code, mit dem Stephen verknüpft ist, zeigt nur eine einfache Verschiebung, ohne den Wert für die rechte Hand zu überprüfen. Wenn ich mich richtig erinnere, verwenden x86-Prozessoren nur die unteren sechs Bits des Verschiebungswerts (im 64-Bit-Modus), sodass das Verhalten möglicherweise direkt von der Maschinensprache abhängt. Außerdem glaube ich, dass Verschiebungen um mehr als die Bitbreite auch in C nicht klar definiert sind ( gccwarnt davor).

ilkkachu
quelle
2

Erzeugen einer ganzen Zahl durch Verschieben eines Bits. Wie weit kann ich gehen?

Bis sich die Ganzzahldarstellung ändert (die Standardeinstellung in den meisten Shells).
Eine 64-Bit-Ganzzahl wird normalerweise um umbrochen 2**63 - 1.
Das ist 0x7fffffffffffffffoder 9223372036854775807im Dezember.

Diese Zahl '+1' wird negativ.

Das ist das Gleiche wie 1<<63:

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

Danach wiederholt sich der Vorgang erneut.

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

Das Ergebnis ist abhängig mod 64vom Verschiebewert [a] .

[a] Aus: Intel® 64- und IA-32-Architekturen Software-Entwicklerhandbuch: Band 2 Die Anzahl wird auf 5 Bit maskiert (oder 6 Bit, wenn im 64-Bit-Modus REX.W verwendet wird). Der Zählbereich ist auf 0 bis 31 begrenzt (oder 63, wenn der 64-Bit-Modus und REX.W verwendet werden). .

Also: denk dran das $((1<<0))ist1

$ 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

Es kommt also darauf an, wie nahe die Zahl einem Vielfachen von 64 kommt.

Testen des Limits:

Der robuste Weg zu testen, welcher die maximale positive (und negative) Ganzzahl ist, besteht darin, jedes einzelne Bit der Reihe nach zu testen. Es sind sowieso weniger als 64 Schritte für die meisten Computer, es wird nicht zu langsam sein.

bash

Zuerst benötigen wir die größte Ganzzahl der Form 2^n(1 Bit gefolgt von Nullen). Wir können das tun, indem wir nach links schieben, bis die nächste Schicht die Zahl negativ macht, auch "Wrap Around" genannt:

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

Wo bist das Ergebnis: Der Wert vor der letzten Schicht, die die Schleife nicht besteht.

Dann müssen wir jedes Bit ausprobieren, um herauszufinden, welche das Vorzeichen von e:

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

Die maximale Ganzzahl ( intmax) ergibt sich aus dem letzten Wert von d.

Auf der negativen Seite (kleiner als 0) wiederholen wir alle Tests, aber testen, wann ein Bit auf 0 gesetzt werden kann, ohne es umzukrempeln.

Ein ganzer Test mit Ausdruck aller Schritte ist (für 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"

Sch

In fast jede Shell übersetzt:

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

Wenn Sie die obigen
Anweisungen für viele Shells ausführen , haben alle (außer bash 2.04 und mksh) Werte bis ( 2**63 -1) in diesem Computer akzeptiert .

Es ist interessant zu berichten, dass die att-Shell :

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

druckte einen Fehler auf Werte von $((2^63)), aber nicht ksh.

Sorontar
quelle