[unix] Bash에서 비트 단위 시프트 및 가장 큰 정수

이것은 탐구 질문입니다.이 질문에 대해 완전히 확신 할 수는 없지만 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



답변

Bash intmax_t산술 변수를 사용 합니다 . 시스템에서 길이는 64 비트이므로 다음과 같습니다.

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

어느

100000000000000000000000000000000000000000000000000000000000000

이진수로 (1 뒤에 62 0). 다시 바꾸십시오.

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

어느

1000000000000000000000000000000000000000000000000000000000000000

2의 보수 산술에서 2 진수 (63 0)로 표시됩니다.

표현 가능한 가장 큰 정수를 얻으려면 1을 빼야합니다.

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

어느

111111111111111111111111111111111111111111111111111111111111111

이진으로.

ilkkachu답변 에서 지적했듯이 shifting은 64 비트 x86 CPU 에서 오프셋 모듈로 64를 사용합니다 ( 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))


답변

보내는 사람 CHANGES의 파일 bash2.05b :

제이. 쉘은 이제 기계가 지원하는 가장 큰 정수 크기 (intmax_t)로 산술을 수행합니다.

x86_64 시스템에서는 intmax_t부호있는 64 비트 정수에 해당합니다. 따라서 -2^63와 사이에 의미있는 값이 2^63-1있습니다. 그 범위를 벗어나면 랩 어라운드가 생깁니다.


답변

이동량이 효과적으로 그래서, 비트 (64)의 수의 모듈로 촬영하기 때문에 1024 이동하면, 하나를 제공 1024 === 64 === 0하고 1025 === 65 === 1.

1시프트 값이 (적어도) 64 이상이되기 전에 상위 비트가 로우 엔드로 둘러싸이지 않기 때문에 a 이외의 다른 것을 시프트 하면 비트 회전이 아님이 분명해집니다.

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

이 동작은 시스템에 따라 다를 수 있습니다. Stephen이 링크bash 코드 는 오른손 값을 확인하지 않고 단순한 변화 보여줍니다. 올바르게 기억한다면 x86 프로세서는 시프트 값의 맨 아래 6 비트 (64 비트 모드) 만 사용하므로 동작은 기계 언어에서 직접 발생할 수 있습니다. 또한 비트 폭보다 큰 시프트는 C에서도 명확하게 정의되지 않았다고 생각합니다 ( gcc경고).


답변

비트를 시프트하여 정수를 생성하는 단계. 얼마나 멀리 갈 수 있습니까?

정수 표현이 끝날 때까지 (대부분의 쉘에서 기본값).
64 비트 정수는 일반적으로로 둘러싸 2**63 - 1입니다.
의 그 0x7fffffffffffffff또는 922337203685477580712월있다.

그 숫자 ‘+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] 출처 : 인텔 ® 64 및 IA-32 아키텍처 소프트웨어 개발자 설명서 : 볼륨 2 카운트는 5 비트 (64 비트 모드에서 REX.W를 사용하는 경우 6 비트)로 마스크됩니다. 카운트 범위는 0에서 31로 제한됩니다 (또는 64 비트 모드 및 REX.W를 사용하는 경우 63). .

또한 : 그 기억 $((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의 배수에 얼마나 가까운 지에 달려 있습니다.

한계 테스트 :

최대 양수 (및 음수) 정수인 강력한 테스트 방법은 각 1 비트를 차례로 테스트하는 것입니다. 어쨌든 대부분의 컴퓨터에서 64 단계 미만이지만 너무 느리지 않습니다.

세게 때리다

먼저 가장 큰 정수 형식이 필요합니다 2^n(1 비트 세트 다음에 0). 다음에 쉬프트 할 때까지 “wrap around”라고 불리는 숫자가 마이너스가 될 때까지 왼쪽으로 쉬프트하면됩니다

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가 아닌의 값에 대한 오류를 인쇄했습니다 .


답변