그레이 코드 변경 위치를 반복하는 효율적인 방법

Question

n-bit Gray codes을 반복하는 여러 가지 방법이 있습니다. 일부는 다른 것보다 효율적입니다. 그러나 실제로 그레이 코드가 필요하지 않으며 그레이 코드 목록에서 변경된 비트 인덱스를 반복하는 대신 실제 그레이 코드를 반복하는 것이 좋습니다. ,

는

000, 001, 011, 010, 110, 111, 101, 100

내가하려는 출력 3, 2, 3 : 예를 들어, 3 비트의 그레이 코드리스트를 가지고 1, 3, 2, 3. 이것은 우리가 목록을 얻기 위해 비트 3, 2, 3 등을 바꿀 필요가 있음을 말해 준다. 여기에서 1부터 왼쪽부터 색인을 생성합니다.

이 작업을 수행하는 한 가지 방법은 회색 코드를 순서대로 계산하고 각 연속 쌍 (x, y)에 대해 (xxOR y)를 계산하여 변경된 비트를 식별 한 다음 정수 로그베이스 2 (x XOR y).

그러나 가능한 한 빨리 반복해야하며 관심사는 30-40 비트 회색 코드입니다.

효율적인 방법이 있습니까?

Answer 1

0으로 시작하는 비트의 번호를 최하위로 지정하면 이진수로 그레이 코드를 증가시키기 위해 변경할 비트의 위치가 증가하는 이진수에 설정된 최하위 비트의 위치입니다 (위키피디아의 끝 부분 참조). 당신이 연결된 단락) - 제시 한 번호 매기기를 얻으려면 3/비트 위치 수를 뺍니다.

binary-reflected ("Gray") 000  001  011  010  110  111  101  100 
binary      001  010  011  100  101  110  111 
pos of least significant 1  0  1  0  2  0  1  0 
(count of trailing zeros ctz) 
3 - ctz(binary)    3  2  3  1  3  2  3 

Answer 2

당신이 (당신은 확실히 당신이 벡터화 할 수 있도록 어셈블리 출력을 미세하게 제어 할 수있는 언어를 사용한다) C GCC의 내장으로, 예를 들어, 함께 작업하는 경우, 당신은

을 수행 할 수 있습니다

long long ctr = 0LL; 
int next() { return __builtin_ctzll(++ctr); } 

이 값은 카운터 ctr의 후미에있는 0을 계산하여 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, ...을 반환합니다.

필요한 경우 번역하십시오.