바이트 배열을 12 비트로 이동하는 방법

https://stackoverflow.com/questions/29437

09-06-2019
|

문제

바이트 배열의 내용을 12 비트 왼쪽으로 이동하고 싶습니다.

예를 들어 다음 유형의 uint8_t shift[10] 배열로 시작합니다. 라코 디스

왼쪽으로 12 비트 이동하여 다음과 같은 결과를 얻고 싶습니다. 라코 디스

해결책

포인터를 위해 만세!

이 코드는 각 바이트에 대해 12 비트를 미리보고 적절한 비트를 앞으로 복사하는 방식으로 작동합니다.12 비트는 다음 바이트의 아래쪽 절반 (니블)이고 2 바이트의 위쪽 절반입니다. 라코 디스 <인용구>

Justin은 다음과 같이 썼습니다.
@Mike, 솔루션은 작동하지만 전달되지 않습니다.

글쎄요, 저는 정상적인 시프트 연산이 바로 그 일을하고 (오버플로라고 함) 여분의 비트가 오른쪽이나 왼쪽으로 떨어지도록합니다.원하는 경우 휴대하기에 충분히 간단합니다. 이동을 시작하기 전에 12 비트 만 저장하면됩니다.오버플로 된 비트를 바닥에 다시 놓기 위해 순환 이동을 원할까요?어레이를 재 할당하고 더 크게 만들고 싶습니까?호출자에게 오버플로를 반환 하시겠습니까?0이 아닌 데이터가 오버플로되면 부울을 반환합니까?캐리가 자신에게 의미하는 바를 정의해야합니다. 라코 디스

다른 팁

여기에 제 해결책이 있지만 더 중요한 것은 문제 해결에 대한 저의 접근 방식입니다.

문제에 접근했습니다

메모리 셀을 그리고 대상에서 소스로 화살표를 그립니다.
위 그림을 보여주는 표를 만들었습니다.
상대 바이트 주소로 표의 각 행에 레이블 지정
다음은 패턴을 보여주었습니다.
- iL를 a[i]의 하위 니블 (하프 바이트)로 설정
- iH를 a[i]의 상위 니블로 설정
- iH = (i+1)L
- iL = (i+2)H
  이 패턴은 모든 바이트에 적용됩니다.
  C로 번역하면 다음을 의미합니다. 라코 디스
  이제 세 가지 관찰을 더합니다.
  - 왼쪽에서 오른쪽으로 할당을 수행하므로 임시 변수에 값을 저장할 필요가 없습니다.
  - 꼬리에 대한 특별한 경우가 있습니다. 끝에있는 모든 12 bits는 0이됩니다.
  - 배열을지나 정의되지 않은 메모리를 읽지 않아야합니다. a[i+2] 이상을 읽지 않기 때문에 마지막 2 바이트에만 영향을 미칩니다.
    그래서 우리
    - N-2 bytes를 반복하고 위의 일반 계산을 수행하여 일반적인 경우를 처리합니다.
    - iH = (i+1)L를 설정하여 마지막 바이트를 처리합니다.
    - 마지막 바이트를 0로 설정하여 처리
      a 길이를 가진 N가 주어지면 다음과 같은 결과를 얻을 수 있습니다. 라코 디스
      그리고 당신은 그것을 가지고 있습니다. 배열은 12 bits에 의해 왼쪽으로 이동됩니다. 그것은 N bits를 이동시키는 것으로 쉽게 일반화 될 수 있으며, M가있는 곳에 M = number of bits modulo 8 할당 문이있을 것이라는 점에 주목합니다.
      포인터로 변환하여 일부 시스템에서 루프를 더 효율적으로 만들 수 있습니다. 라코 디스
      CPU에서 지원하는 가장 큰 정수 데이터 유형을 사용합니다.
      (방금 입력했기 때문에 누군가가 코드를 검토하기에 좋은 시간이 될 것입니다. 특히 비트 트위들 링이 잘못되기 쉽기 때문입니다.)

8 비트 정수 배열에서 유전자 태그 코드 비트를 이동하는 가장 좋은 방법입니다. 라코 디스

여기에서이 데이터를 사용하여 배열의 정수를 이동하는 가장 최적의 방법을 찾아야 할 것 같습니다. 일반 알고리즘은 배열의 오른쪽에서 시작하여 각 정수 유전자 태그 코드 인덱스를 이동하여 전체 정수 시프트를 적용하는 것입니다. 0은 새로 빈 공간을 채 웁니다. 그런 다음 마지막으로 오른쪽에서 다시 시작하여 모든 인덱스에 대해 유전자 태그 코드 비트 시프트를 수행합니다.

N를 F 비트로 이동하는 경우에는 bitwise AND를 수행하고 bitshift 연산자를 사용하여 shift를 수행하여 오버플로를 계산할 수 있습니다. 라코 디스

4 비트는 단순한 마스크 (0x0F 또는 0b00001111) 일뿐입니다. 계산하기 쉽고 동적으로 빌드하거나 간단한 정적 조회 테이블을 사용할 수도 있습니다.

충분히 일반적 이길 바랍니다. 나는 C / C ++에 전혀 익숙하지 않기 때문에 누군가가 내 구문을 정리하거나 더 구체적 일 수 있습니다.

보너스 : C를 능숙하게 사용하는 경우 여러 배열 인덱스를 단일 16, 32 또는 64 비트 정수로 퍼지하고 이동을 수행 할 수 있습니다. 그러나 그것은 그다지 이식성이 좋지 않으며 이에 대해 권장 할 것입니다. 가능한 최적화입니다.

다음은 임시 변수를 사용하는 작업 솔루션입니다. 라코 디스

12 비트 시프트를 위해이 함수를 3 번 호출합니다.

임시 변수를 사용하기 때문에 Mike의 솔루션이 더 빠를 수 있습니다.

32 비트 버전 ... :-) 1 <= count <= num_words 처리 라코 디스

@Joseph, 변수의 폭은 8 비트이고 시프트 폭은 12 비트입니다.솔루션은 N <= 가변 크기에서만 작동합니다.

배열이 4의 배수라고 가정 할 수 있다면 배열을 uint64_t 배열로 캐스팅 한 다음 작업 할 수 있습니다.4의 배수가 아닌 경우 64 비트 청크에서 가능한 한 많이 작업하고 나머지는 하나씩 작업 할 수 있습니다. 이것은 약간 더 코딩이 될 수 있지만 결국에는 더 우아하다고 생각합니다.

이를 깔끔한 문제로 만드는 몇 가지 극단적 인 경우가 있습니다.

입력 배열이 비어있을 수 있습니다.
마지막 및 다음에서 마지막 비트는 0 비트가 이동되어 있으므로 특별히 처리해야합니다. 다음은 다음 바이트의 하위 니블을 상위 니블에 복사하고 다음 바이트 (+2) 바이트의 상위 니블을 하위에 복사하는 배열을 반복하는 간단한 솔루션입니다. 한입 깨물기. 미리보기 포인터를 두 번 역 참조하는 것을 저장하기 위해 "마지막"및 "다음"바이트가있는 두 요소 버퍼를 유지합니다. 라코 디스
기능의 더 많은 부분을 연속적으로 활성화하는 경계 사례를 고려하십시오.
- length가 0이면 우리는 기억을 건드리지 않고 구제합니다.
- length가 1이면 우리는 유일한 요소를 0으로 설정합니다.
- length가 2 인 경우 첫 번째 바이트의 상위 니블을 두 번째 바이트 (즉, 비트 12 ~ 16)의 하위 니블로 설정하고 두 번째 바이트를 0으로 설정합니다. 루프를 활성화하지 않습니다.
- length가 2보다 크면 루프에 도달하여 두 요소로 구성된 버퍼에서 바이트를 섞습니다.
  효율성이 목표라면 대답은 주로 컴퓨터의 아키텍처에 달려 있습니다. 일반적으로 두 요소 버퍼를 유지해야하지만 한 번에 기계어 (32/64 비트 부호없는 정수)를 처리해야합니다. 많은 데이터를 이동하는 경우 처음 몇 바이트를 특수한 경우로 취급하여 기계어 포인터를 워드로 정렬 할 수 있도록하는 것이 좋습니다. 대부분의 CPU는 액세스가 머신 워드 경계에 해당하는 경우 메모리에 더 효율적으로 액세스합니다. 물론 후행 바이트도 특별히 처리해야하므로 배열 끝을 지나서 메모리를 건드리지 않습니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow