단일 곱셈으로 비트 추출

단일 곱셈으로 비트 추출

다른 질문에 대한 답변에 사용된 흥미로운 기술을 보고 조금 더 이해하고 싶습니다.

부호 없는 64비트 정수가 주어지고 다음 비트에 관심이 있습니다.

1.......2.......3.......4.......5.......6.......7.......8.......

특히 다음과 같이 상위 8개 위치로 이동하고자 합니다.

12345678........................................................

하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, , 하다, 하다, 하다, 하다, 하다, , 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다, 하다..보존할 필요가 없습니다.

해결책은 불필요한 비트를 가리고 결과를 곱하는 것이었습니다.0x2040810204081이게 효과가 있음이 밝혀졌습니다.

이 방법은 얼마나 일반적인가요?이 기술을 사용하여 비트의 서브셋을 추출할 수 있습니까?그렇지 않은 경우 이 방법이 특정 비트세트에 대해 기능하는지 여부를 어떻게 확인할 수 있습니까?

마지막으로, 주어진 비트를 추출하기 위해 올바른 승수를 찾는 방법은 무엇입니까?

매우 흥미로운 질문이고, 영리한 속임수입니다.

1바이트를 조작하는 간단한 예를 보겠습니다.단순성을 위해 부호 없는 8비트를 사용합니다.의 는 ★★★★★★★★★★★★★★★★★★★★★★.xxaxxbxx은 '그냥'을 원한다.ab000000.

이 솔루션은 두 단계로 구성되었습니다. 즉, 약간의 마스킹과 곱셈입니다.비트 마스크는 중요하지 않은 비트를 0으로 변환하는 단순한 AND 연산입니다.경우 는 「」가 .00100100 그 "" " " " " " " " "00a00b00

어려운 점은 그걸 '이거'로 바꾸면ab.......

곱셈은 시프트 앤 애드 연산입니다.핵심은 오버플로를 허용하여 불필요한 비트를 "쉬프트 아웃"시키고 원하는 비트를 올바른 위치에 배치하는 것입니다.

(4의 곱셈)00000100는 남은 을 모두 ( )으로 합니다.a00b0000b위로 이동하려면 1에 (a를 올바른 위치에 유지하려면) + 4(b를 위로 이동하려면)를 곱해야 합니다.이고, 즉 4가 됩니다.00010100★★★★★★★★★★★★★★★★★.00a00b00스스,, 음음음음음 음음음음음음

000000a00b000000
00000000a00b0000 +
----------------
000000a0ab0b0000
xxxxxxxxab......

이 방법을 사용하면 더 큰 숫자와 더 많은 비트로 확장할 수 있습니다.

어느새'는 '어느새?'안 된다'는한 '안 된다'라고 합니다.몇 번의 마스킹 작업이나 몇 번의 곱셈을 허용하지 않는 한 대답은 "아니오"라고 생각합니다.문제는 '충돌' 문제입니다.b'를 사용하다. 해 보세요.xaxxbxxcx. 접근법에 {2, { + =x-에 대한 가 앞의 접근법에 따르면 {x 2, x {1 + 4 + 16}} = x 42 (OOH - 모든 것의 해답!)가 필요하다고 생각됩니다.★★★★

00000000a00b00c00
000000a00b00c0000
0000a00b00c000000
-----------------
0000a0ababcbc0c00
xxxxxxxxabc......

보시다시피, 여전히 작동하지만 "그냥"입니다.여기서 중요한 것은 모든 것을 압축할 수 있는 "충분한 공간"이 필요한 부분 사이에 있다는 것입니다.c 바로 뒤에 4번째 비트d를 추가할 수 없었습니다.c+d를 얻으면 비트가 전송할 수 있는 인스턴스가 생기기 때문입니다.

그래서 공식적인 증거가 없다면, 저는 당신의 질문의 더 흥미로운 부분에 대해 다음과 같이 대답할 것입니다. "아니요, 이것은 어떤 비트수에도 효과가 없습니다.N비트를 추출하려면 추출할 비트 사이에 (N-1) 공백이 필요하거나 마스크 멀티플 스텝이 추가로 필요합니다."

「비트간에 (N-1) 제로가 필요」규칙에 대해서 생각할 수 있는 유일한 예외는, 이것 뿐입니다.원래의 2비트를 서로 인접해 있는 2비트를 추출해, 같은 순서로 하고 싶은 경우는, 그대로 할 수 있습니다.(N-1) 규칙에서는 2비트로 카운트됩니다.

아래 @Ternary의 답변에서 영감을 얻은 또 다른 통찰력이 있습니다(내 코멘트는 이쪽 참조).각 대상 비트에 대해 오른쪽으로 이동해야 하는 비트를 위한 공간이 필요한 만큼만 0이 필요합니다.또한 왼쪽에 결과 비트가 있는 만큼 왼쪽에 비트가 필요합니다.따라서 비트 b가 n의 위치m에 도달한 경우 왼쪽에 m-1 0, 오른쪽에 n-m 0이 있어야 합니다.특히 순서 변경 후와 같은 원래 번호의 순서가 아닌 경우, 이것은 원래 기준에 대한 중요한 개선입니다.예를 들어 16비트 단어가

a...e.b...d..c..

전환 가능

abcde...........

, 에 두 개, 것 에 세 개, 즉 b 사 1 、 d 와 c 、 2 、 개 3 개 。N-1은요? 「」는,a...e'되고 수 1블록'이 됩니다.이러한 블록에 1을 곱하면 올바른 위치에 도달하기 때문에 "e를 공짜로 얻을 수 있습니다."b와 d도 마찬가지입니다(b는 오른쪽에 3칸, d는 왼쪽에 3칸 필요).따라서 매직 넘버를 계산하면 중복되는 것이 발견됩니다.

a: << 0  ( x 1    )
b: << 5  ( x 32   )
c: << 11 ( x 2048 )
d: << 5  ( x 32   )  !! duplicate
e: << 0  ( x 1    )  !! duplicate

이 숫자들의 순서를 바꾸려면 공백이 더 있어야 합니다. ''을 할 수 있어요.(N-1)규칙: "비트에 (N-1) 이상의 공백이 있는 경우, 또는 최종 결과에서 비트 순서를 알고 있는 경우, 비트 b가 m의 위치에 있는 경우, 왼쪽에 m-1의 0, 오른쪽에 n-m의 0이 있어야 합니다.

@Ternary는 "타깃 영역 바로 오른쪽에"를 추가하는 비트로부터의 반송이 있을 수 있기 때문에 이 규칙이 제대로 작동하지 않는다고 지적했다. 즉, 우리가 찾는 비트가 모두 하나일 때 말이다.위에서 설명한 16비트 단어로 된5개의 촘촘히 포장된 비트로 예를 이어가겠습니다.

a...e.b...d..c..

하기 위해 비트 .ABCDEFGHIJKLMNOP

우리가 하려고 했던 수학은

ABCDEFGHIJKLMNOP

a000e0b000d00c00
0b000d00c0000000
000d00c000000000
00c0000000000000 +
----------------
abcded(b+c)0c0d00c00

이든 아래에 것으로 생각했다.abcde (비밀(이행)ABCDE)는되지 만, @Ternary가 지적한 바와 같이 @Ternary가 지적한 바와 같이b=1, c=1, d=1(b+c)G는, 시킵니다.F ,, ②,(d+1)F에 조금 영향을 미칠 것이다E가 엉망이 - 결과가 엉망이 됐어요.비트 공간( 「」 「」 「」 「」 「」)에해 주세요.c이 예에서는)는 문제가 되지 않습니다. 왜냐하면 곱셈은 beyone에서 0으로 채워지는 가장 낮은 비트의 패딩을 일으키기 때문입니다.

따라서 (m-1)/(n-m) 규칙을 수정해야 합니다.사용하지 않는 비트가 오른쪽에 정확히 (n-m) 있는 비트가 두 개 이상 있는 경우(위의 예에서 패턴의 마지막 비트는 "c"로 카운트되지 않음), 규칙을 강화해야 하며 반복해야 합니다.

는 (하는 비트 (1) 수도 를 Q0 Q0)로n-mQ1(n-m+1), Q(N-1)(n-1)입니다. 을 감수해야 한다.

Q0 > 1
Q0 == 1 && Q1 >= 2
Q0 == 0 && Q1 >= 4
Q0 == 1 && Q1 > 1 && Q2 >=2
... 

이걸 보시면 간단한 수식을 쓰면 알 수 있어요.

W = N * Q0 + (N - 1) * Q1 + ... + Q(N-1)

는 ★★★★★★★★★★★★★★★★.W > 2 * N 후 합니다.(n-m+1)W < 4안 될 더 등 그래도 안 될 경우 기준을 하나 더 높이는 등

이상과 같이 하면 답변에 큰 도움이 될 것 같습니다.

정말 흥미로운 질문입니다.저는 제 2센트를 참고하겠습니다. 비트벡터 이론에 대한 1차 논리로 이런 문제를 설명할 수 있다면 정리프로바이저는 여러분의 친구입니다. 그리고 잠재적으로 여러분의 질문에 대한 매우 빠른 답을 제공할 수 있습니다.질문되는 문제를 정리로서 다시 설명하겠습니다.

"모든 64비트 비트 벡터 x에 대해 y = (x & mask) * 승수로 y.63 == x.63, y.62 == x.55, y.61 == x.47 등을 갖는 64비트 상수 '마스크' 및 '마스크'가 존재합니다."

만약 이 문장이 사실 정리라면, 정수 '마스크'와 '승수'의 일부 값이 이 성질을 만족시킨다는 것은 사실이다.정리 프로버가 이해할 수 있는, 즉 SMT-LIB 2 입력의 관점에서 설명하겠습니다.

(set-logic BV)

(declare-const mask         (_ BitVec 64))
(declare-const multiplicand (_ BitVec 64))

(assert
  (forall ((x (_ BitVec 64)))
    (let ((y (bvmul (bvand mask x) multiplicand)))
      (and
        (= ((_ extract 63 63) x) ((_ extract 63 63) y))
        (= ((_ extract 55 55) x) ((_ extract 62 62) y))
        (= ((_ extract 47 47) x) ((_ extract 61 61) y))
        (= ((_ extract 39 39) x) ((_ extract 60 60) y))
        (= ((_ extract 31 31) x) ((_ extract 59 59) y))
        (= ((_ extract 23 23) x) ((_ extract 58 58) y))
        (= ((_ extract 15 15) x) ((_ extract 57 57) y))
        (= ((_ extract  7  7) x) ((_ extract 56 56) y))
      )
    )
  )
)

(check-sat)
(get-model)

이제 정리프로버 Z3에게 이것이 정리인지 물어봅시다.

z3.exe /m /smt2 ExtractBitsThroughAndWithMultiplication.smt2

결과는 다음과 같습니다.

sat
(model
  (define-fun mask () (_ BitVec 64)
    #x8080808080808080)
  (define-fun multiplicand () (_ BitVec 64)
    #x0002040810204081)
)

빙고! 원래 게시물에 주어진 결과를 0.06초 만에 재현합니다.

이것을 보다 일반적인 관점에서 보면, 우리는 이것을 1차 프로그램 합성 문제의 일례라고 볼 수 있다.이것은 아직 발표된 논문의 수가 적은 연구의 초기 영역이다.「 」의 "program synthesis" filetype:pdf시작하셔야 합니다.

승수의 모든 1비트는 다음 중 하나의 비트를 올바른 위치에 복사하는 데 사용됩니다.

• 1는 이미 위치에 , 을.0x0000000000000001.
• 2 위치를 에 7비트를 . 그래서 우리는 곱합니다.0x0000000000000080(일곱 살)
• 3 14비트를 . 그래서 우리는 곱합니다.0x0000000000000400(14일)
• 등까지
• 8 49비트 위치에 49비트를 . 그래서 우리는 곱합니다.0x0002000000000000(49년)

승수는 개별 비트에 대한 승수의 합계입니다.

이것은 수집하는 비트가 서로 너무 가깝지 않기 때문에 스킴에서 함께 속하지 않는 비트의 곱셈이 64비트를 넘거나 하위의 상관없는 부분에서 떨어지기 때문입니다.

는 """로 해야 .0AND and and and and and and and and and 。

(처음 봐.이 트릭은 훌륭해!)

더 ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★n한 n-1"CHANGE: "CHANGE: "CHANGE: " 。

처음에는 더 잘 할 수 있을 것 같다는 생각이 들었습니다." " " " 를 하는 n 추출 시 i이 i에 기재되어 있습니다.i-1 앞 비트 앞n-i비트가 계속됩니다.

몇 가지 예를 들어 설명하겠습니다.

...a..b...c...다보다 없음).a와 after의 , " " " "b이전 2비트에는 아무도 없습니다.c):

  a00b000c
+ 0b000c00
+ 00c00000
= abc.....

...a.b....c...실패 이유b그 후 2비트에 있습니다.a(그리고 우리가 교대할 때 다른 사람의 자리에 끌려간다.)a):

  a0b0000c
+ 0b0000c0
+ 00c00000
= abX.....

...a...b.c...실패 이유b앞의 2비트에 있습니다.c(그리고 우리가 교대할 때 다른 사람의 자리에 밀어넣어진다.c):

  a000b0c0
+ 0b0c0000
+ b0c00000
= Xbc.....

...a...bc...d...연속 비트가 함께 이동하므로 작동합니다.

  a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000

하지만 문제가 있습니다.를 사용하는 경우n-i대신n-1다음과 같은 시나리오를 생각할 수 있습니다.마지막에는 뭔가 숨기고 싶지만 중요한 비트의 반송 비트가 중요한 비호환 범위에 간섭하게 되면 어떻게 될까요?(주:n-1요구 사항으로 인해 이 문제가 발생하지 않도록 하기 위해i-1비트의 비트는 비트의 비트가 클리어 되어 있습니다.i비트)

...a...b..c...d...캐리 비트에 장애가 발생할 수 있습니다.c인n-1끝나고b단, 만족합니다.n-i기준:

  a000b00c000d
+ 0b00c000d000
+ 00c000d00000
+ 000d00000000
= abcdX.......

그럼 다시 그 이야기로 돌아가면 어떨까?n-1'스페이스 비트의' 요건더 잘 할 수 있기 때문입니다.

...a....b..c...d.. "에 실패했습니다.n-1bits of space" 테스트를 수행하지만 비트 변환 트릭에서는 다음과 같이 동작합니다.

+ a0000b00c000d00
+ 0b00c000d000000
+ 00c000d00000000
+ 000d00000000000
= abcd...0X......

이러한 분야를 특징짓는 좋은 방법이 떠오르지 않습니다.n-1중요한 비트 사이의 간격은 유지되지만, 여전히 우리의 작업에는 효과가 있습니다.단, 어떤 비트에 관심이 있는지 미리 알고 있기 때문에 필터를 확인하여 캐리어 비트 충돌이 발생하지 않는지 확인할 수 있습니다.

비교하다(-1 AND mask) * shift기대했던 결과와 비교해서-1 << (64-n)(64비트 부호 없음의 경우)

비트를 추출하는 매직 시프트/멀티 기능은 두 비트가 동일한 경우에만 작동합니다.

이 매우 흥미로운 질문에 대한 이미 훌륭한 대답 외에도, 이 비트 곱셈 기술은 2007년부터 컴퓨터 체스 커뮤니티에서 알려져 왔으며, Magic BitBoards라는 이름으로 사용되고 있다는 것을 아는 것이 유용할 수 있다.

많은 컴퓨터 체스 엔진은 여러 개의 64비트 정수(비트보드라고 함)를 사용하여 다양한 피스 세트(점유된 정사각형당 1비트)를 나타냅니다.특정 원점 사각형에서 슬라이딩 조각(룩, 비숍, 퀸)이 최대 다음 위치로 이동할 수 있다고 가정합니다.K블록 조각이 없는 경우 정사각형.비트를 사용하여 흩어진 것 중 하나를 사용합니다.K점유된 정사각형의 비트보드를 가진 비트는 특정 정보를 준다K- 64비트 정수 내에 포함된 비트 워드입니다.

매직 곱셈을 사용하여 이 산란된 맵을 만들 수 있습니다.K아래쪽에 있는 비트K64비트 정수의 비트이것들 더 낮은 것K그런 다음 비트를 사용하여 원점 정사각형 상의 조각이 실제로 이동할 수 있는 허용된 정사각형을 나타내는 사전 편집된 비트 보드의 테이블을 인덱싱할 수 있습니다(블록 조각 처리 등).

이 방법을 사용하는 일반적인 체스 엔진은 사전 계산된 결과를 포함하는 64개의 엔트리(원점 제곱당 1개) 중 2개의 테이블(루크용, 비숍용, 퀸용)을 가지고 있다.최고 등급의 폐쇄 소스(후디니)와 오픈 소스 체스 엔진(Stockfish) 모두 매우 높은 성능을 위해 현재 이 접근법을 사용하고 있습니다.

이러한 매직 승수를 찾는 작업은 철저한 검색(조기 컷오프에 의해 최적화됨) 또는 시행착오(예: 랜덤 64비트 정수를 많이 시도함)를 사용하여 수행됩니다.이동 생성 중에 사용된 비트 패턴이 없으며 마법 상수를 찾을 수 없습니다.단, 일반적으로 비트 반송 효과는 매핑되는 비트에 인접 인덱스가 (거의) 있는 경우에 필요합니다.

AFAIK는 @Syzygy에 의한 매우 일반적인 SAT-솔러 접근법은 컴퓨터 체스에서 사용되지 않았고, 그러한 마법 상수의 존재와 고유성에 관한 공식적인 이론도 없는 것으로 보인다.

언급URL : https://stackoverflow.com/questions/14547087/extracting-bits-with-a-single-multiplication