전치 행렬의 연속 요소를 효율적으로 반복 (비트 연산자를 통해)

Question

1 차원 배열로 내부적으로 표현되는 행렬을 생각해 봅시다. 예를 들어 행렬 (3, 4)은 실제로는 배열 (double 유형) 또는 3 * 4 요소입니다. 여기서 행렬의 '메모리 레이아웃': 그것은 반복하는 것은 매우 간단 이와 같이

00 01 02 03 
04 05 06 07 
08 09 10 11 

(행 단위는 왼쪽에서 오른쪽으로) 행렬의 모든 요소 위에 :이가는 단지 32 비트 정수이다

00 04 08 
01 05 09 
02 06 10 
03 07 11 

입력 으로 전치 행렬의 i 번째 요소 (나타내는 단일 32 비트 정수를 취하는 (고속) 알고리즘이란 11. 0 내지이 전치의 모습이며 행별로, 왼쪽에서 오른쪽으로) 내부 표현에 해당하는 인덱스를 반환합니까? 싱글이라 함은 'incremental'알고리즘이 내가 찾고있는 것이 아니라, 함수가 단지 하나의 32 비트 정수 (더하기 행과 열 수)를 입력으로 받아서 하나의 32 비트 정수를 출력한다는 것을 의미한다. 비트 단위 연산자는 문제를 해결하는 가장 빠른 방법 일 수 있지만 실제로는 효율적인 솔루션으로 충분합니다. 위의 예에서 : 또한

0 --> 0 
1 --> 4 
2 --> 8 
3 --> 1 
4 --> 5 
5 --> 9 
6 --> 2 
... 

, 제한 (있는 경우)의 행과 열 수를 부과 할 필요가 있도록 (우리가 이미 num_row이 * num_col는 32 비트 정수에 맞는) 알고리즘은 작동하도록 보장됩니다.

감사합니다.

Answer 1

만큼 크기가 작은 남아있는 한, 당신은 조회 테이블로 상수를 사용할 수 있습니다 : 그들은 약간 커질 경우

0x4cd0b73a62951840 >> (x*4)) & 15 

, 당신은 예를 들어, 이것을 분할 수 결과의 상위 및 하위 비트를 생성 :

((0x00fea540 >> (x*2)) & 3) | (((0x00924924 >> (x*2) & 3) << 2)) 

을 결국 비록 직진 접근 빠를 것이다.