Побитовый сдвиг и наибольшее целое число в Bash

16

Это вопрос исследования, то есть я не совсем уверен, о чем этот вопрос, но я думаю, что это самое большое целое число в Bash. Во всяком случае, я буду определять это реже.

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

Я делаю целое число, немного сдвигая. Как далеко я могу пойти?

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

Не так далеко, по-видимому. (1 неожиданно, и я вернусь к нему.) Но,

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

все еще положительный. Не это, однако:

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

И на шаг дальше,

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

Почему 1? И почему следующее?

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

Кто-то хотел бы проанализировать эту серию?

ОБНОВИТЬ

Моя машина:

$ 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
Жиль "ТАК - прекрати быть злым"
источник
-9223372036854775808 = 0xF333333333333334. Это забавно выглядящий крайний случай. Конечно, 4611686018427387904 = 0x4000000000000000. Я подозреваю, что вы попадаете в какое-то сокращение числа битов, на которое нужно сдвинуться. В любом случае, зачем ты это делаешь?
CVn
6
@ MichaelKjörling Для развлечения ;-p
2
@ MichaelKjörling Нет, это не так. -9223372036854775808 будет 0x8000000000000000. Вы пропустили последнюю цифру при проверке: -922337203685477580 будет 0xF333333333333334.
HVd

Ответы:

27

Bash использует intmax_tпеременные для арифметики . В вашей системе они имеют длину 64 бита, поэтому:

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

который

100000000000000000000000000000000000000000000000000000000000000

в двоичном формате (1 с последующим 62 0). Сдвиньте это снова:

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

который

1000000000000000000000000000000000000000000000000000000000000000

в двоичном (63 0 с), в арифметике дополнения до двух.

Чтобы получить наибольшее представимое целое число, вам необходимо вычесть 1:

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

который

111111111111111111111111111111111111111111111111111111111111111

в двоичном

Как было отмечено в ilkkachu «s ответ , сдвигая берет смещение по модулю 64 на 64-разрядных x86 процессоров (независимо от использования RCLили SHL), который объясняет поведение , которое вы видите:

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

эквивалентно $((1<<0)). Таким образом , $((1<<1025))это $((1<<1)), $((1<<1026))это $((1<<2))...

Вы найдете определения типов и максимальные значения в stdint.h; в вашей системе:

/* 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))
Стивен Китт
источник
1
Нет, они вам нужны, бинарный -имеет более высокий приоритет, чем <<.
Cuonglm
1
@cuonglm да, мне подходит для тестирования на Zsh ... Еще раз спасибо!
Стивен Китт
@cuonglm и Стивен. Ну, это хорошее редактирование. echo $((1<<63-1))дает мне 4611686018427387904.
@tomas yup, bash использует приоритет оператора C, zsh имеет собственный по умолчанию, где $((1<<63-1))равно $(((1<<63)-1)).
Стивен Китт
Это полезно знать, хороший вопрос и очень подробный ответ, благодаря вам, как Стивену Китту, так и Томасу.
Валентин Борисович
4

Из CHANGESфайла для bash2.05b:

к. Оболочка теперь выполняет арифметику с наибольшим целочисленным размером, поддерживаемым машиной (intmax_t) вместо long.

На машинах x86_64 intmax_t соответствует 64-разрядным целым числам со знаком. Таким образом, вы получаете значимые значения между -2^63и 2^63-1. За пределами этого диапазона вы просто получаете обходы.

Сату Кацура
источник
Nitpick: между -2^63и 2^63-1включительно.
Номинальное животное
4

Сдвиг на 1024 дает единицу, потому что величина сдвига эффективно берется по модулю количества бит (64), а значит 1024 === 64 === 0, и 1025 === 65 === 1.

Сдвиг чего-то другого, кроме a, 1дает понять, что это не битовое вращение, поскольку старшие биты не переходят в нижний предел, пока значение сдвига не станет (как минимум) 64:

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

Может случиться так, что это поведение зависит от системы. Код bash, на который ссылается Стивен, показывает просто сдвиг, без какой-либо проверки правого значения. Если я правильно помню, процессоры x86 используют только младшие шесть битов значения сдвига (в 64-битном режиме), поэтому поведение может быть напрямую из машинного языка. Кроме того, я думаю, что сдвиги более чем на битовую ширину также не определены четко в C ( gccпредупреждает об этом).

ilkkachu
источник
2

производя целое число, сдвигая немного. Как далеко я могу пойти?

Пока целочисленное представление не оборачивается (по умолчанию в большинстве оболочек).
64-битное целое число обычно переносится в 2**63 - 1.
Это 0x7fffffffffffffffили 9223372036854775807в дек.

Это число «+1» становится отрицательным.

Это так же, как 1<<63, таким образом:

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

После этого процесс повторяется снова.

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

Результат зависит mod 64от значения сдвига [a] .

[a] От: Руководство разработчика программного обеспечения для архитектуры Intel® 64 и IA-32: Том 2 Счетчик маскируется до 5 бит (или 6 бит, если в 64-битном режиме используется REX.W). Диапазон счета ограничен от 0 до 31 (или 63, если используется 64-битный режим и REX.W). ,

Также: помните, что $((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

Итак, все зависит от того, насколько близко число к кратному 64.

Тестирование лимита:

Надежный способ проверить, какое максимальное положительное (и отрицательное) целое число - это проверить каждый бит по очереди. В любом случае, для большинства компьютеров он менее 64 шагов, и он не будет слишком медленным.

удар

Сначала нам нужно самое большое целое число в форме 2^n(1 бит, за которым следуют нули). Мы можем сделать это, сдвигая влево, пока следующий сдвиг не сделает число отрицательным, также называемое «обтекание»:

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

где b результат: значение перед последним сдвигом, который не проходит цикл.

Затем нам нужно попробовать каждый бит, чтобы выяснить, какие из них влияют на признак e:

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

Максимальное целое число ( intmax) является результатом последнего значенияd .

На отрицательной стороне (меньше чем 0 ) мы повторяем все тесты, но тестируем, когда бит можно сделать равным 0, не оборачиваясь.

Целый тест с печатью всех шагов таков (для 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"

ш

Переводится практически на любую оболочку:

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

При выполнении вышеуказанного для многих оболочек
все (кроме bash 2.04 и mksh) принимали значения до (2**63 -1 ) на этом компьютере.

Интересно сообщить, что оболочка att :

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

вывел ошибку на значениях $((2^63)), а не ksh.

sorontar
источник