왜 링 버퍼 크기가 2의 거듭 제곱이어야합니까?

Question

왜 링 버퍼 크기가 2의 거듭 제곱이어야합니까?

Answer 1

아래에 설명 된 방법을 사용하려면 2의 거듭 제곱이어야합니다. 그렇지 않아도됩니다.

일반적인 접근 방식은 "if (index> = size) {index = size - index;}"와 같습니다 (크기 10, 색인 10, 결과 색인은 0 임). 이것은 다음과 같은 접근법에 비해 느리고 오류가 발생하기 쉽습니다. - 31로

size = 32 
bin(size) => '00100000' 

mask = size - 1; 
bin(mask) => '00011111' 

비트 단위로이 마스크를 적용하고, 우리는 0의 범위에 숫자를 포함하는 경우에만 비트를 분리 할 수 ​​있습니다 : 2의 거듭 제곱을 사용하여

는

우리는 다음을 활용할 수 색인은 다음과 같이 커집니다.

index = 4 
bin(4 & mask) => '00000100' (4) 

# index 32 wraps. note here that we do no bounds checking, 
# no manipulation of the index is necessary. we can simply 
# and safely use the result. 
index = 32 
bin(index & mask) => '00000000' (0) 

index = 33 
bin(index & mask) => '00000001' (1) 

index = 64 
bin(index & mask) => '00000000' (0) 

index = 65 
bin(index & mask) => '00000001' (1) 

이 접근 방식은 비교가 필요없고 분기가없고 안전합니다 (결과 색인은 항상 범위 내입니다). 정보를 삭제하지 않는 이점이 있습니다. 인덱스 65는 엘리먼트 1을 다루지 만, 나는 여전히 인덱스가 논리적으로 65라는 정보를 가지고있다.

나는 또한 인덱스 (버퍼에 주소 13) 3456237로 성장 때 나는 파티에 늦었을 알고 3.

을 때 같이 이것은 단지 효율적입니다 추가 할, 나는 '이 질문을 어떻게 발견했는지 모르겠다. :-) 희망이 도움이된다.