64비트 레지스터에서 select

갑자기 64비트 레지스터에서 select를 조작하고 싶을 때 있어요.비트 연산 기술 Advent Calendar 19일째 보도다.

이른바 select

select_q (k) 는 그룹 x에서 시작할 때 k에서 나오는 값 q의 인덱스를 되돌려 주는 함수로 정의됩니다.예를 들어 배열[0,0,0,1,1,0,1,0,1,0,1,0,1,0,1]의 경우(왼쪽으로 시작)select1(3)=6.
이 select의 연산에서 64비트 레지스터는 64개 요소의 {0, 1} 배열로 간주되며, 때로는 그 위에서 실행하려고 할 수도 있습니다.이것은 succinct 데이터 structure의 상하문에 나타납니다.(나는 다른 목적이다)

저기 pdep 나왔어요.

x86_intel은 64에서 BMI2 명령 그룹을 가져왔으며 pdep이라는 명령이 있습니다.

이렇게 마스크 레지스터 scatter를 사용하여 src 아래에서 배열된 위치입니다.이것을 사용하여 64비트 레지스터 v에 select-계산 1 (k).

1을 왼쪽으로 k로 이동하고 select의 벡터를 마스크로 pdep하여 결과의 레지스터 tzcnt (아래위 0) 를 사용합니다.또 v의 1개 수가 k개 이하일 때 pdep 중 1이 쫓겨나 64가 됐다.이동, pdep, tzcnt는 모두 3개의 시계가 필요하기 때문에 빠르지는 않지만, 분기가 없는 것이 좋다.대단히 기쁘다.

끝말

나는 pdep가 국제 장기와 장기에서만 사용하는 줄 알았는데 뜻밖에도 스스로 사용한 것이라 놀랐다. 이런 사용 방법이 있다는 것을 발견하고 매우 기뻤다.나는 이 놀라움과 기쁨을 누구에게...