비트 twiddling 재주문

StackOverflow https://stackoverflow.com/questions/624538

  •  05-07-2019
  •  | 
  •  

문제

나는 7 비트 값의 임의의 재주문을 수행해야하며 (예, 테이블을 사용해야한다는 것을 알고 있습니다)이를 수행 할 비트 핵이 있는지 궁금합니다.

예시:

// <b0, b1, b2, b3, b4, b5, b6> -> <b3, b2, b4, b1, b5, b0, b6>

// the naive way
out =
   (0x020 & In) << 5 |
   (0x008 & In) << 2 |
   (0x040 & In)      |
   (0x012 & In) >> 1 |
   (0x004 & In) >> 2 |
   (0x001 & In) >> 3;

// 6 ANDs, 5 ORs, 5 shifts = 16 ops

편집하다:나는 선을 따라 무언가를 생각하고 있었다 이것

킥을 위해서와 나는 후미 였기 때문에 양식의 솔루션을 위해 무차별 인력 검색을 시도하고 있습니다.

((In * C1) >> C2) & 0x7f

해결책이 없습니다.

도움이 되었습니까?

해결책

"순진한"코드의 컴파일러 출력을 살펴보면 놀랄 수도 있습니다. 나는 한때 그런 일을했고 컴파일러 (VC ++ 2005)는 모든 ands의 값을 완전히 바꾸었고 더 효율적으로 만들기 위해 교대 근무를했습니다. 예를 들어 "(0x001 & in) >> 삼".

그러나 예, 개편이 고정 된 기능이라면 테이블이 가장 좋을 것입니다.

업데이트

웃음을 위해 VC ++ 2005의 컴파일러 출력을 보았습니다 ....

먼저 "in"에 대한 일정한 값을 시도했지만 컴파일러는 한 번에 속지 않았 으며이 코드를 생성했습니다.

mov eax,469h

즉. 완전히 최적화했습니다.

그래서 ... 나는 적절한 입력을 시도하고 이것을 얻었습니다.

00401D4F  mov         eax,ecx 
00401D51  and         eax,20h 
00401D54  shl         eax,3 
00401D57  mov         edx,ecx 
00401D59  and         edx,8 
00401D5C  or          eax,edx 
00401D5E  mov         edx,ecx 
00401D60  sar         edx,1 
00401D62  and         edx,2 
00401D65  or          edx,ecx 
00401D67  sar         edx,1 
00401D69  shl         eax,2 
00401D6C  and         edx,9 
00401D6F  or          eax,edx 
00401D71  and         ecx,40h 
00401D74  or          eax,ecx

그것은 4 개의 Shift 작업, 5 ands, 4 ors로 6 개의 입력에 나쁘지 않습니다. 아마도 대부분의 사람들이 손으로 할 수있는 것보다 낫습니다.

아마도 순서 외 실행에 최적화되어있을 것이므로 보이는 것보다 시계 사이클이 적을 것입니다. :-)

다른 팁

첫 번째 단계는 수학적 솔루션을 이해하고 최적화하는 것 같습니다.

여기를 참조하십시오 비트 핵

일반적인 운영을위한 비트 전형 해킹이 많이 있습니다. 즉, 비트의 순서를 32 비트 단어 (10 개의 교대 및 및 afaicr)로 역전시키기위한 것입니다.

이 경우 입력에서 출력까지 완전히 임의의 매핑을 사용하면이를 청소하는 방법을 볼 수 없습니다.

조회 테이블을 사용하십시오 :)

최적화하기 전에 '순진한'방식이 의도 한 일을하고 있는지 확인해야합니다. 코드를 함수로 만들고이 루프를 실행하면 :

for (b=0;b<7;b++)
{
    i=1<<b;
    printf("%d: %02x -> %02x\n", b, i, shuffle(i));
}

이 출력을 생성하여 의견과 모순됩니다. 사실, 그것은 비트를 잃습니다.

0: 01 -> 00
1: 02 -> 01
2: 04 -> 01
3: 08 -> 20
4: 10 -> 08
5: 20 -> 00
6: 40 -> 40

설명하는 셔플을 얻으려면 다음과 같이 코딩 할 것입니다.

   //    0 1 2 3 4 5 6 
   //-> 3 2 4 1 5 0 6
   (0x001 & In) << 3 |
   (0x004 & In) << 2 |
   (0x020 & In)      |
   (0x012 & In) << 1 |
   (0x008 & In) >> 2 |
   (0x020 & In) >> 5 ;
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top