첫 번째 세트 찾기

Find first set

컴퓨터 소프트웨어 및 하드웨어에서 첫 번째 세트(ffs)를 찾거나 첫 번째 세트(fffs)를 찾거나 첫 번째 세트(first find)는 부호 없는 기계어가 [nb 1]주어졌을 때 최하위 비트 위치에서 워드 카운트 중 1로 설정된 최하위 비트의 인덱스 또는 위치를 지정하는 비트 연산이다.거의 동등한 연산은 count trailing 제로(ctz) 또는 trailing 제로(ntz)의 수이며, 최하위 1비트에 이은 제로 비트 수를 카운트합니다.최상위 세트비트의 인덱스 또는 위치를 찾는 상보연산은 로그베이스 2입니다.이러한 연산은 바이너리 로그 「log2(x)」[1]를 계산하기 위해서입니다.이는 최상위 [nb 2]1비트 앞의 0비트 수를 카운트하는 선행 0(clz) 또는 선행 0(nlz)의 수와 밀접하게 관련되어 있습니다.find first set에는 두 가지 일반적인 변형이 있습니다.[2]1부터 비트의 인덱싱을 시작하는 POSIX 정의(여기서는 ffs라벨이 붙어 있습니다)와 0부터 비트의 인덱싱을 시작하는 변종은 ctz와 같기 때문에 이 이름으로 불립니다.

대부분의 최신 CPU 명령 집합 아키텍처는 이들 중 하나 이상을 하드웨어 오퍼레이터로 제공합니다.소프트웨어 에뮬레이션은 보통 컴파일러 내장 또는 시스템 라이브러리에서 사용할 수 없는 모든 것을 위해 제공됩니다.

예

다음 32비트 단어가 지정됩니다.

0000 0000 0000 0000 1000 0000 0000 1000

count trailing zero 연산에서는 3이 반환되고 count leading zero 연산에서는 16이 반환됩니다.선두 제로 카운트 조작은 워드 크기에 따라 달라집니다.이 32비트 워드가 16비트 워드로 잘린 경우 선두 제로 카운트는 0을 반환합니다.첫 번째 세트 찾기 작업은 오른쪽에서 네 번째 위치를 나타내는 4를 반환합니다.로그 베이스 2는 15 입니다.

마찬가지로 다음 32비트 워드의 경우 위의 워드의 비트 단위 부정:

1111 1111 1111 1111 0111 1111 1111 0111

count trailing 1s 연산은 3, count leading 1s 연산은 16, find first 0 연산 ffz는 4를 반환합니다.

워드가 0(비트 세트 없음)인 경우 선행 0 카운트 및 후행 0 카운트 모두 워드의 비트 수를 반환하고 ffs는 0을 반환합니다.로그 기반 2와 find first set의 제로 기반 구현 모두 일반적으로 제로 워드에 대해 정의되지 않은 결과를 반환합니다.

하드웨어 지원

많은 아키텍처에는 아래에 나열된 첫 번째 집합 찾기 및/또는 관련 작업을 신속하게 수행하는 지침이 포함되어 있습니다.가장 일반적인 연산은 count leading 0(clz)으로, 다른 모든 연산은 count leading zero(clz)와 관련하여 효율적으로 구현될 수 있기 때문일 수 있습니다(속성과 관계 참조).

플랫폼 니모닉 이름. 오퍼랜드 폭 묘사 0에 적용 시
ARM(ARMv5T 아키텍처 이후)
Cortex-M0/M0+/M1/M23 제외		 클릭하다[3] 선행 제로의 카운트 32 클릭하다 32
ARM(ARMv8-A 아키텍처) 클릭하다 선행 제로의 카운트 32, 64 클릭하다 오퍼랜드 폭
AVR32 클릭하다[4] 선행 제로의 카운트 32 클릭하다 32
DEC 알파 ctlz[5] 선행 제로의 카운트 64 클릭하다 64
CTTTZ[5] 후행 제로 수 64 ctz 64
인텔 80386 이후 bsf[6] 비트 스캔 전송 16, 32, 64 ctz 정의되지 않았습니다. 제로 플래그를 설정합니다.
bsr[6] 비트 스캔 리버스 16, 32, 64 로그 베이스 2 정의되지 않았습니다. 제로 플래그를 설정합니다.
BMI1 또는 ABM을 지원하는 x86 동작하지[7] 않다 선행 제로의 카운트 16, 32, 64 클릭하다 오퍼랜드 폭, 반송 플래그 설정
BMI1을 지원하는 x86 하지[8] 않다 후행 제로 수 16, 32, 64 ctz 오퍼랜드 폭, 반송 플래그 설정
아이테니엄 클릭하다[9] 선행 제로의 카운트 64 클릭하다 64
MIPS32/MIPS64 클릭하다[10][11] Word 선행 0 카운트 32, 64 클릭하다 오퍼랜드 폭
클로[10][11] Word에서 선행 항목 수 32, 64 클로 오퍼랜드 폭
Motorola 68020 이후 bfffo[12] 비트 필드에서 첫 번째 항목 찾기 임의 로그 베이스 2 필드 오프셋 + 필드 폭
PDP-10 쟈포 첫 번째 항목을 찾으면 점프 36 ctz 0, 동작 없음
POWER / PowerPC / Power ISA cntlz/cntlzw/cntlzd[13] 선행 제로의 카운트 32, 64 클릭하다 오퍼랜드 폭
Power ISA 3.0 이후 cnttzw/cnttzd[14] 후행 제로 수 32, 64 ctz 오퍼랜드 폭
RISC-V ('B' 확장자) (드래프트) 클릭하다[15] 선행 제로의 카운트 32, 64 클릭하다 오퍼랜드 폭
ctz[15] 후행 제로 수 32, 64 ctz 오퍼랜드 폭
SPARC Oracle 아키텍처 2011 이후 lzcnt(표준: lzd)[16] 선두 제로 카운트 64 클릭하다 64
VAX ffs[17] 첫 번째 세트 찾기 0–32 ctz 오퍼랜드 폭, 제로 플래그 설정
IBM z/아키텍처 플로피[18] 왼쪽 끝 찾기 64 클릭하다 64
비디오[18] 0을 선행하는 벡터 수 8, 16, 32, 64 클릭하다 오퍼랜드 폭
모니터[18] 벡터 카운트 후행 0 8, 16, 32, 64 ctz 오퍼랜드 폭

일부 Alpha 플랫폼에서는 CTLZ 및 CTTZ가 소프트웨어로 에뮬레이트됩니다.

도구 및 라이브러리 지원

많은 컴파일러 및 라이브러리 벤더가 컴파일러 내장 함수 또는 라이브러리 함수를 제공하여 첫 번째 세트 찾기 및/또는 관련 작업을 수행합니다.이러한 기능은 위의 하드웨어 지침에 따라 자주 구현됩니다.

공구/라이브러리 이름. 유형 입력 유형 메모들 0에 적용 시
POSIX.1 준거 libc
4.3BSD libc
OS X 10.3 libc[2][19]		 ffs 라이브러리 기능 인트 glibc를 포함합니다.POSIX는 보충 로그베이스 2 / clz를 제공하지 않습니다. 0
FreeBSD 5.3 libc
OS X 10.4 libc[19]		 ffsl
fls
flsl		 라이브러리 기능 int,
긴		 fls"find last set")는 (로그 베이스 2) + 1을 계산합니다. 0
FreeBSD 7.1 libc[20] ffsll
flsll		 라이브러리 기능 오래오래 0
GCC 3.4.0[21][22]
쨍그랑 5.x[23][24]		 __builtin_ffs[l,ll,imax]
__builtin_clz[l,ll,imax]
__builtin_ctz[l,ll,imax]
 내장 기능 서명되지 않은 int,
서명 없는 긴 길이,
서명 없는 긴 길이,
uintmax_t		 GCC 문서에서는 정의되지 않은 clz와 ctz가 0으로 간주됩니다. 0(ffs)
Visual Studio 2005 _BitScanForward[25]
_BitScanReverse[26]		 컴파일러 기능 서명 없는 긴 길이,
부호 없음 __int64		 입력이 0임을 나타내는 반환값 구분 정의되어 있지 않다
Visual Studio 2008 __lzcnt[27] 컴파일러 고유 부호 없는 쇼트,
서명되지 않은 int,
부호 없음 __int64		 BMI1 또는 ABM에서 도입된lzcnt 명령의 하드웨어 지원에 의존합니다. 오퍼랜드 폭
Visual Studio _arm_clz[28] 컴파일러 고유 부호 없는 int ARMv5T 아키텍처 이후에 도입된 clz 명령의 하드웨어 지원에 의존합니다. ?
인텔 C++ 컴파일러 _bit_scan_forward
_bit_scan_reverse[29][30]		 컴파일러 기능 인트 정의되어 있지 않다
NVIDIA CUDA[31] __clz 기능들 32비트, 64비트 GeForce 400 시리즈에 대한 보다 적은 명령으로 컴파일 32
__ffs 0
LLVM llvm.ctlz.*
llvm.cttz.*[32]		 본질적 8, 16, 32, 64, 256 LLVM 어셈블리 언어 피연산자 폭(두 번째 인수가 0인 경우), 그렇지 않으면 정의되지 않음
GHC 7.10(베이스 4.8), inData.Bits[필요한 건] countLeadingZeros
countTrailingZeros		 라이브러리 기능 FiniteBits b => b 해스켈 프로그래밍 언어 오퍼랜드 폭
C++20 표준 라이브러리, 헤더 내<bit>[33][34] bit_ceil bit_floor
bit_width
countl_zero countl_one
countr_zero countr_one		 라이브러리 기능 부호 없는 문자,
부호 없는 쇼트,
서명되지 않은 int,
서명 없는 긴 길이,
부호 없는 긴 길이

속성 및 관계

비트가 1(이 문서에서 사용하는 규칙)부터 시작하는 경우, 후행 0을 카운트하고 첫 번째 설정 연산 찾기는 ctz(x) = ffs(x) - 1(입력 0인 경우 제외)로 관련됩니다.비트가 0에서 시작하는 경우, 후행 0을 카운트하고 첫 번째 세트를 찾는 작업은 정확히 동일합니다.워드당 w비트가 주어지면 로그는2 log(x) = w - 1 - clz(x)로2 clz에서 쉽게 계산됩니다.

위의 예에서 알 수 있듯이 find first zero, count leading one 및 count trailing 1 조작은 입력을 부정하고 first set, count leading 0 및 count trailing 0을 사용하여 구현할 수 있습니다.그 반대도 사실이다.

M68000 등 로그2 조작이 효율적인 플랫폼에서는 ctz는 다음과 같이 계산할 수 있습니다.

ctz(x) = log2(x & -x)

여기서 &은 비트의 AND를 나타내고 -x는 x의 두 개의 보완을 나타냅니다.x & -x 표현은 최하위1비트를 제외한 모든 비트를 클리어하기 때문에 최하위1비트와 최하위1비트는 동일합니다.

ARM이나 PowerPC 등의 효율적인 카운트 선행 제로 동작이 있는 플랫폼에서는 ffs는 다음과 같이 계산할 수 있습니다.

ffs(x) = w - clz(x & -x).

반대로 로그 연산자 또는 clz 연산자가 없는2 머신에서는 clz는 비효율적이지만 ctz를 사용하여 계산할 수 있습니다.

clz = w - ctz(2⌈log2(x)⌉)(영점 입력에 대해 w를 반환하는 ctz에 따라 다름)

SPARC와 같은 효율적인 해밍 중량(인구 수) 연산을 가진 플랫폼에서는POPC[35][36] 또는 Blackfin'sONES,[37] 다음이 있습니다.

ctz(x) = popcount((x & -x) - [38][39]1) 또는 ctz(x) = popcount(~(x -x)),
ffs(x) = popcount(x ^ ~-x)[35]
clz = 32 - popcount (2⌈log2(x)⌉ - 1)

여기서 ^은 비트 배타적 논리합, 비트 배타적 논리합, ~는 비트 부정을 나타냅니다.

역문제(i가 주어지면, ctz(x) = i)가 왼쪽 시프트(1 < < i)로 계산될 수 있는 x를 생성한다.

Find first set 및 관련 조작은 한쪽 끝에서 시작하여 all-zero(fffs, ctz, clz의 경우) 또는 all-one(fz, clo, cto의 경우)이 아닌 단어가 나타날 때까지 진행함으로써 임의의 대규모 비트 어레이로 쉽게 확장할 수 있습니다.비트맵을 재귀적으로 사용하여 0이 아닌 단어를 추적하는 트리 데이터 구조는 이를 가속화할 수 있습니다.

소프트웨어 에뮬레이션

1980년대 후반 이후 대부분의 CPU에는 ffs 또는 동등한 비트 연산자가 있지만 ARM-Mx 시리즈와 같은 일부 최신 CPU에는 비트 연산자가 없습니다.ffs, clz 및 ctz의 하드웨어 연산자 대신 소프트웨어는 시프트, 정수 연산자 및 비트 연산자를 사용하여 이들을 에뮬레이트할 수 있습니다.CPU의 아키텍처와 프로그래밍 언어 의미론 및 컴파일러 코드 생성 품질에 따라 몇 가지 접근법이 있습니다.접근법은 선형 검색, 이진 검색, 검색+테이블 검색, de Bruijn 곱셈, 부동소수점 변환/exponent 추출 및 비트 연산자(브랜치리스) 메서드로 대략 설명될 수 있습니다.실행 시간과 스토리지 공간 사이에는 이동성과 효율성뿐만 아니라 트레이드오프도 있습니다.

소프트웨어 에뮬레이션은 일반적으로 결정론적입니다.이들은 모든 입력 값에 대해 정의된 결과를 반환합니다. 특히, 모든 0비트의 입력에 대한 결과는 보통 ffs의 경우 0이고 다른 작업에 대한 피연산자의 비트 길이는 0입니다.

하드웨어 clz 또는 동등한 것이 있는 경우 비트 연산을 사용하여 ctz를 효율적으로 계산할 수 있지만, 그 반대는 사실이 아닙니다.clz는 하드웨어 연산자가 없는 경우 계산이 효율적이지 않습니다.

2개n

시프트 및 비트 단위[40] OR을 사용하는 함수⌈log2(x)⌉ 2(2의 가장 가까운 제곱)는 다음 32비트 예시와 같이 계산하기에는 효율적이지 않으며 64비트 또는 128비트 피연산자가 있는 경우에는 더욱 비효율적입니다.

함수 pow2(x): x = 0 return invalid // invalid가 구현 정의되어 있는 경우([0,63]이 아님) x ← x - 1이 {1, 2, 4, 8, 16}의 각 y: x ← x (x > y)가 x + 1을 반환합니다.

FFS

ffs = ctz + 1(POSIX) 또는 ffs = ctz(기타 구현)이므로 ctz에 적용할 수 있는 알고리즘을 사용할 수 있으며, 결과에 1을 더하고 모든 0 비트의 입력에 대해 피연산자 길이 대신 0을 반환하는 가능한 마지막 단계를 수행할 수 있습니다.

CTZ

표준 알고리즘은 1비트가 발생할 때까지 LSB에서 시작하는 루프 카운트0 입니다

함수 ctz1(x)은 x = 0이 반환되는 경우 w t ← 1 r ← 0인 반면 (x & t) = 0 t ← t < 1 r ← r + 1 return r

이 알고리즘은 O(n) 시간 및 연산을 실행하며 다수의 조건부 분기로 인해 실제로는 실행이 불가능합니다.

룩업 테이블은 대부분의 브랜치를 제거할 수 있습니다.

테이블[0..]2-1n] = i의 경우 ctz(i)(0.2-1n) 함수 ctz2(x)의 경우 x = 0 return w r ← 0 루프(x & (2-1n))의 경우 θ 0 return r + table [x & (2-1n)]x ← x > n r ← r + n

매개 변수 n은 고정(일반적으로 8)이며 시간-공간 균형을 나타냅니다.루프가 완전히 풀릴 수도 있습니다.그러나 선형 룩업으로서 이 접근법은 오퍼랜드 내의 비트수에서는 여전히 O(n)입니다.

바이너리 검색의 실장은,[41][42] 다음의 32비트 버전과 같이, 로그의 조작과 브랜치를 필요로 합니다.이 알고리즘은 테이블에서도 지원할 수 있으며, 맨 처음 발견된 0 이외의 바이트를 인덱스로 사용하여 하위 3개의 "if" 문을 256개의 엔트리 룩업 테이블로 대체할 수 있습니다. 

함수 ctz3(x)는 x = 0이 32n을 반환하는 경우 32n ← 0(x & 0x0000FFF) = 0:n ← n + 16, x ← x > 16(x & 0x00000000)의 경우 16(x & 0x0000000000)FF) = 0:n ← n + 8, x ← x > 8 if (x & 0x000000000F) = 0:n ← n + 4, x ← 4 if (x & 0x0000000003) ← 0:n ← n + 2, x > 2 if (x & 0x00000000000001 + n = 0: 0: n)

하드웨어에 clz 연산자가 있는 경우 ctz를 계산하는 가장 효율적인 방법은 다음과 같습니다.

함수 ctz4(x) x &= -x 반환 w - (clz(x) + 1)

32비트 ctz 알고리즘은 de Bruijn 시퀀스를 사용하여 모든 [43][44]분기를 제거하는 최소 완전 해시 함수를 구축합니다.이 알고리즘에서는 곱셈 결과가 32비트로 잘린 것으로 가정합니다. 

i가 0 ~ 31인 경우: table [ ( 0 x 077 )CB531 * ( 1 < i ) >> 27 ]← i // 테이블[ 0 .31] 초기화 함수 ctz5 (x) 리턴 테이블 [(x & -x) * 0x077CB531)>> 27 ]

식(x & -x)은 다시 최하위1비트를 분리합니다.부호 없는 곱셈과 시프트 해시가 표의 올바른 위치에 있는 32개의 단어만 사용할 수 있습니다.(이 알고리즘에서는 제로 입력은 처리되지 않습니다).

CLZ

표준 알고리즘은 MSB에서 시작하여 다음 예시와 같이 0이 아닌 비트가 발견될 때까지 한 번에 한 비트를 검사합니다.O(n) 시간 내에 실행됩니다.여기서 n은 피연산자의 비트 길이이며 일반적인 용도로는 실용적인 알고리즘이 아닙니다. 

함수 clz1 (x)이 x = 0 반환 w t ← 1 < (w - 1) r ← 0인 반면 (x & t) = 0 t >> 1 r ← r + 1 반환 r

이전 루프 접근 방식의 개선에서는 한 번에8비트를 검사하고 첫 번째 비제로 바이트에 256(28) 엔트리 룩업테이블을 사용합니다.그러나 이 접근방식은 실행 시간에서는 아직 O(n)입니다. 

함수 clz2 (x)가 x = 0 return w t ← 0xff < (w - 8) r ← 0, 반면 (x & t) = 0 t ← t >> 8 r ← r + 8 return r + table [x >> (w - 8 - r ) ]

바이너리 검색을 통해 실행 시간을 O(logn2)로 줄일 수 있습니다. 

x = 0인 경우 함수 clz3 (x)는 32n ← 0인 경우(x & 0xFF)를 반환합니다.FF0000) = 0:n ← n + 16, x ← 16 if (x & 0xFF00000000) = 0:n ← n + 8 if (x & 0xF0000000) = 0:n ← n + 4, x < 4 if (x & 0x00000000000000)

clz를 시뮬레이션하는 가장 빠른 휴대용 접근법은 이진 검색과 테이블 검색의 조합입니다. 8비트 테이블 검색(2=256 1바이트 엔트리)은8 이진 검색의 하위 3개 분기를 대체할 수 있습니다. 64비트 오퍼랜드는 추가 분기가 필요합니다.보다 넓은 폭의 룩업을 사용할 수 있지만, 최신 프로세서의 L1 데이터 캐시 크기(대부분의 경우 32KB)에 의해 실제 최대 테이블 크기가 제한됩니다.L1 캐시 미스의 지연으로 브랜치 저장이 상쇄되는 것은 아닙니다.

CTZ용 de Bruijn 곱셈과 유사한 알고리즘은 CLZ에서는 기능하지만 최상위 비트를 분리하는 것이 아니라 시프트 및 비트 단위 OR을 [45]사용하여 형식의n 가장 가까운 정수로 반올림합니다.

테이블[0..]31] = {0, 9, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 27, 23, 6, 26, 5, 4, 31} 함수 clz4 (x) (x) :

Prescott 및 이후의 인텔 프로세서 등 파이프라인이 깊은 프로세서의 경우 예측이 빗나간 브랜치의 파이프라인 플러시를 피하기 위해 브랜치를 비트 단위의 AND 연산자와 OR 연산자로 교체하는 것이 더 빠를 수 있습니다(단, 많은 명령어가 필요함). 

함수 clz5 (x) r = (x > 0xFF) << 4 ; x >> = r; q = (x > 0xFF ) << 3 ; x > = q ; q = (x > 0xF ) < 2 ; x > r = q ; = q > < x > 1 > < 3 >

정수를 부동소수로 하드웨어 변환하는 플랫폼에서는 지수 필드를 정수에서 추출하고 감산하여 선행 0의 카운트를 계산할 수 있습니다.반올림 오류를 [41][46]고려하려면 수정이 필요합니다.부동소수점 변환은 상당한 지연 시간을 가질 수 있습니다.이 방법은 휴대성이 매우 낮기 때문에 일반적으로 권장되지 않습니다. 

인트 x;  인트 r; 조합 { 서명되어 있지 않다 인트 u[2]; 이중으로 하다 d; } t;  t.u[LE] = 0x43300000;  // LE는 little-endian의 경우 1입니다. t.u[!LE] = x; t.d -= 4503599627370496.0; r = (t.u[LE] >> 20) - 0x3FF;  // log2 r++;  // CLZ

적용들

count leading zero(clz) 연산은 m × 2로e 정수를 인코딩하는 정규화를 효율적으로 구현하기 위해 사용할 수 있습니다. 여기서 m은 알려진 위치(가장 높은 위치 등)에 최상위 비트가 있습니다.이는 다시 뉴턴-라프슨 나눗셈을 구현하고, 소프트웨어 및 기타 애플리케이션에서 [41][47]정수로 부동소수점 변환을 수행하는 데 사용할 수 있습니다.

count leading 0(clz)을 사용하여 ID를 통해 32비트 술어 "x = y"(참이면 0, 거짓이면 1)를 계산할 수 있습니다.clz(x - y) >>> 5 。여기서 ">"는 부호 없는 오른쪽 [48]시프트입니다.n개의 1비트의 [49]첫 번째 스트링을 찾는 등 보다 정교한 비트 연산을 수행하기 위해 사용할 수 있습니다.clz(x - y)1 < < (16 - clz(x - 1)/2)는 뉴턴의 [50]방법을 사용하여 32비트 정수의 제곱근을 계산하는 데 효과적인 초기 추측입니다.CLZ는 null [51]suppression을 효율적으로 구현할 수 있습니다.이는 정수를 선두의 0바이트 수와 함께 부호화하는 고속 데이터 압축 기술입니다.또한 균일하게 랜덤한 [41]정수의 clz를 취함으로써 지수 분포 정수를 효율적으로 생성할 수 있습니다.

로그 베이스2 는, 「log22(xy)」+ 「log2(y)」[52]이기 때문에, 곱셈이 오버플로우 할지를 예측하기 위해서 사용할 수 있습니다.

Count leading 0과 count trailing 0은 제한된 자원을 [42]사용하여 유한 범위의 함수의 주기를 찾을 수 있는 Gosper의 루프 검출 [53]알고리즘을 구현하기 위해 함께 사용할 수 있습니다.

바이너리 GCD 알고리즘은 후행 0을 삭제하는 데 많은 사이클을 소비합니다.이것은 Count Trailing Zero(ctz; 카운트 후행 0)와 시프트로 대체할 수 있습니다.비슷한 루프가 우박 시퀀스의 계산에도 나타난다.

비트 어레이를 사용하여 priority 큐를 구현할 수 있습니다.이러한 맥락에서 find first set(ffs)은 "팝" 또는 "pull high priority element" 작업을 효율적으로 구현하는 데 유용합니다.Linux 커널 실시간스케줄러는 내부적으로sched_find_first_bit()이 목적을 [54]위해.

제로 카운트 트레일링 조작은 하노이 타워 문제에 대한 심플한 최적의 해결책을 제공합니다.디스크는 0부터 번호가 매겨지고 이동 시 디스크 번호 ctz(k)는 가능한 한 오른쪽으로 이동합니다(필요에 따라 왼쪽으로 돌아가기).또한 임의 워드를 사용하여 [42]k단계에서 비트 ctz(k)를 플립하여 그레이 코드를 생성할 수 있습니다.

「 」를 참조해 주세요.

메모들

  1. ^ 부호 없는 기계어 이외의 비트 연산을 사용하면 정의되지 않은 결과가 나올 수 있습니다.
  2. ^ 다음의 4개의 조작에서는, 무효화 버전(대부분의 경우는)도 있습니다.
    • 최하위 제로 비트의 지수를 식별하는 첫 번째 제로(ffz)를 찾습니다.
    • count trailing ones : 최하위 제로비트 뒤에 이어지는1비트 수를 카운트합니다.
    • 선두 비트 카운트: 최상위 제로 비트 앞의 1비트 수를 카운트합니다.
    • 이진 로그의 역 버전인 최상위 0비트의 인덱스를 찾습니다.

레퍼런스

  1. ^ 앤더슨.MSB N이 O(N) 연산에 설정된 정수의 로그 기준 2를 찾습니다(명확한 방법).
  2. ^ a b "FFS(3)". Linux Programmer's Manual. The Linux Kernel Archives. Retrieved 2012-01-02.
  3. ^ "ARM Instruction Reference > ARM general data processing instructions > CLZ". ARM Developer Suite Assembler Guide. ARM. Retrieved 2012-01-03.
  4. ^ "AVR32 Architecture Document" (PDF) (CORP072610 ed.). Atmel Corporation. 2011. 32000D–04/201. Archived from the original (PDF) on 2017-10-25. Retrieved 2016-10-22.
  5. ^ a b Alpha Architecture Reference Manual (PDF). Compaq. 2002. pp. 4-32, 4-34.
  6. ^ a b Intel 64 and IA-32 Architectures Software Developer Manual. Vol. 2A. Intel. pp. 3-92–3-97. 주문번호 325383입니다.
  7. ^ AMD64 Architecture Programmer's Manual Volume 3: General Purpose and System Instructions (PDF). Vol. 3. Advanced Micro Devices (AMD). 2011. pp. 204–205. Publication No. 24594.
  8. ^ "AMD64 Architecture Programmer's Manual, Volume 3: General-Purpose and System Instructions" (PDF). AMD64 Technology (Version 3.28 ed.). Advanced Micro Devices (AMD). September 2019 [2013]. Publication No. 24594. Archived (PDF) from the original on 2019-09-30. Retrieved 2014-01-02.
  9. ^ Intel Itanium Architecture Software Developer's Manual. Volume 3: Intel Itanium Instruction Set. Vol. 3. Intel. 2010. pp. 3:38. Archived from the original on 2019-06-26.
  10. ^ a b MIPS Architecture For Programmers. Volume II-A: The MIPS32 Instruction Set (Revision 3.02 ed.). MIPS Technologies. 2011. pp. 101–102.
  11. ^ a b MIPS Architecture For Programmers. Volume II-A: The MIPS64 Instruction Set (Revision 3.02 ed.). MIPS Technologies. 2011. pp. 105, 107, 122, 123.
  12. ^ M68000 Family Programmer's Reference Manual (Includes CPU32 Instructions) (PDF) (revision 1 ed.). Motorola. 1992. pp. 4-43–4-45. M68000PRM/AD. Archived from the original (PDF) on 2019-12-08.
  13. ^ Frey, Brad. "Chapter 3.3.11 Fixed-Point Logical Instructions". PowerPC Architecture Book (Version 2.02 ed.). IBM. p. 70.
  14. ^ "Chapter 3.3.13 Fixed-Point Logical Instructions - Chapter 3.3.13.1 64-bit Fixed-Point Logical Instructions". Power ISA Version 3.0B. IBM. pp. 95, 98.
  15. ^ a b Wolf, Clifford (2019-03-22). "RISC-V "B" Bit Manipulation Extension for RISC-V" (PDF). Github (Draft) (v0.37 ed.). Retrieved 2020-01-09.
  16. ^ Oracle SPARC Architecture 2011. Oracle. 2011.
  17. ^ VAX Architecture Reference Manual (PDF). Digital Equipment Corporation (DEC). 1987. pp. 70–71. Archived (PDF) from the original on 2019-09-29. Retrieved 2020-01-09.
  18. ^ a b c "Chapter 22. Vector Integer Instructions". IBM z/Architecture Principles of Operation (PDF) (Eleventh ed.). IBM. March 2015. pp. 7-219–22-10. SA22-7832-10. Retrieved 2020-01-10.
  19. ^ a b "FFS(3)". Mac OS X Developer Library. Apple, Inc. 1994-04-19. Retrieved 2012-01-04.
  20. ^ "FFS(3)". FreeBSD Library Functions Manual. The FreeBSD Project. Retrieved 2012-01-04.
  21. ^ "Other built-in functions provided by GCC". Using the GNU Compiler Collection (GCC). Free Software Foundation, Inc. Retrieved 2015-11-14.
  22. ^ "GCC 3.4.0 ChangeLog". GCC 3.4.0. Free Software Foundation, Inc. Retrieved 2015-11-14.
  23. ^ "Clang Language Extensions - chapter Builtin Functions". The Clang Team. Retrieved 2017-04-09. Clang supports a number of builtin library functions with the same syntax as GCC
  24. ^ "Source code of Clang". LLVM Team, University of Illinois at Urbana-Champaign. Retrieved 2017-04-09.
  25. ^ "_BitScanForward, _BitScanForward64". Visual Studio 2008: Visual C++: Compiler Intrinsics. Microsoft. Retrieved 2018-05-21.
  26. ^ "_BitScanReverse, _BitScanReverse64". Visual Studio 2008: Visual C++: Compiler Intrinsics. Microsoft. Retrieved 2018-05-21.
  27. ^ "__lzcnt16, __lzcnt, __lzcnt64". Visual Studio 2008: Visual C++: Compiler Intrinsics. Microsoft. Retrieved 2012-01-03.
  28. ^ "ARM intrinsics". Visual Studio 2012: Visual C++: Compiler Intrinsics. Microsoft. Retrieved 2022-05-09.
  29. ^ "Intel Intrinsics Guide". Intel. Retrieved 2020-04-03.
  30. ^ Intel C++ Compiler for Linux Intrinsics Reference. Intel. 2006. p. 21.
  31. ^ NVIDIA CUDA Programming Guide (PDF) (Version 3.0 ed.). NVIDIA. 2010. p. 92.
  32. ^ "'llvm.ctlz.*' Intrinsic, 'llvm.cttz.*' Intrinsic". LLVM Language Reference Manual. The LLVM Compiler Infrastructure. Retrieved 2016-02-23.
  33. ^ Smith, Richard (2020-04-01). N4861 Working Draft, Standard for Programming Language C++ (PDF). ISO/IEC. pp. 1150–1153. Retrieved 2020-05-25.
  34. ^ "Standard library header <bit>". cppreference.com. Retrieved 2020-05-25.
  35. ^ a b SPARC International, Inc. (1992). "A.41: Population Count. Programming Note" (PDF). The SPARC architecture manual: version 8 (Version 8 ed.). Englewood Cliffs, New Jersey, USA: Prentice Hall. pp. 231. ISBN 978-0-13-825001-0.
  36. ^ Warren, Jr., Henry S. (2013) [2002]. Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.
  37. ^ Blackfin Instruction Set Reference (Preliminary ed.). Analog Devices. 2001. pp. 8–24. Part Number 82-000410-14.
  38. ^ Dietz, Henry Gordon. "The Aggregate Magic Algorithms". University of Kentucky. Archived from the original on 2019-10-31.
  39. ^ Isenberg, Gerd (2019-11-03) [2012]. "BitScanProtected". Chess Programming Wiki (CPW). Archived from the original on 2020-01-09. Retrieved 2020-01-09.
  40. ^ 앤더슨.다음으로 큰 2의 곱으로 반올림합니다.
  41. ^ a b c d 워렌, 5-3장: 선행 0을 세다.
  42. ^ a b c 워렌, 5-4장: 후행 0을 세다.
  43. ^ Leiserson, Charles E.; Prokop, Harald; Randall, Keith H. (1998-07-07). "Using de Bruijn Sequences to Index a 1 in a Computer Word" (PDF). MIT Laboratory for Computer Science, Cambridge, MA, USA. Archived (PDF) from the original on 2020-01-09. Retrieved 2020-01-09.
  44. ^ Busch, Philip (2009-03-01) [2009-02-21]. "Computing Trailing Zeros HOWTO" (PDF). Archived (PDF) from the original on 2016-08-01. Retrieved 2020-01-09.
  45. ^ 앤더슨.곱셈 및 조회를 사용하여 O(lg(N) 연산에서 N비트 정수의 로그 기반 2를 찾습니다.
  46. ^ 앤더슨.64비트 IEEE 플로트를 사용하는 정수의 정수 로그 베이스2 를 찾습니다.
  47. ^ Sloss, Andrew N.; Symes, Dominic; Wright, Chris (2004). ARM system developer's guide designing and optimizing system software (1 ed.). San Francisco, CA, USA: Morgan Kaufmann. pp. 212–213. ISBN 978-1-55860-874-0.
  48. ^ 워렌, 2-11장: 비교 술어
  49. ^ 워렌. 6-2장: 주어진 길이의 1비트의 첫 번째 문자열을 찾습니다.
  50. ^ 워렌 11-1장 정수 제곱근
  51. ^ Schlegel, Benjamin; Gemulla, Rainer; Lehner, Wolfgang (June 2010). Fast integer compression using SIMD instructions. Proceedings of the Sixth International Workshop on Data Management on New Hardware (DaMoN 2010). pp. 34–40. CiteSeerX 10.1.1.230.6379. doi:10.1145/1869389.1869394. ISBN 978-1-45030189-3.
  52. ^ 워렌, 2장 12절: 오버플로우 감지
  53. ^ Gosper, Bill (April 1995) [1972-02-29]. Baker, Jr., Henry Givens (ed.). "Loop detector". HAKMEM (retyped & converted ed.). Cambridge, Massachusetts, USA: Artificial Intelligence Laboratory, Massachusetts Institute of Technology (MIT). AI Memo 239 Item 132. Archived from the original on 2019-10-08. Retrieved 2020-01-09.
  54. ^ Aas, Josh (2005-02-17). Understanding the Linux 2.6.8.1 CPU Scheduler (PDF). Silicon Graphics, Inc. (SGI). p. 19. Archived (PDF) from the original on 2017-05-19. Retrieved 2020-01-09.

추가 정보

외부 링크