인터뷰 질문이 있었기 때문에 비공식적 인 해결책이 될 수 있습니다.계속되는 비트 길이 1 스트림 뒤에 0
당신은 1이 설정 비트 여기 가정 할 수있다 1.
의 1111 ... 111100000 ... 000
찾기 길이 (수)의 큰 흐름이 말해.
1 심볼 인 경우가 변경됩니다 방법, aaa..aaaabbbb ... BBBBB 내가 제안 할 수
하나 개의 솔루션은 다음 다음 3을 보면 같은 간격을 두 배로 유지하는 1 비트/기호 모양처럼 말 다음 7 일. 0 또는 다른 기호를 눌렀을 때 마지막 위치로 다시 이동하고 다시 나누기와 정복을 사용하십시오.
스트림에 임의로 액세스 할 수 있고 스트림의 길이를 알고있는 경우 O (log n)의 이진 검색 변형을 사용하여 수행 할 수 있습니다.
& 0x1을 사용하고 0이면 카운터 및 오른쪽 시프트를 1 씩 증가시킬 수 있습니다. 또는 전체 바이트 (단어, 더블 워드, 쿼드 워드 등)가 0이 아닌지 신속하게 확인할 수 있습니다 시작 블록을 찾으십시오. 어느 쪽이든 그것은 O (n)입니다.
_stream_에 임의 액세스하는 것은 거의 없습니다. –
빅 비트/심볼 배열이 주어진 것으로 가정합니다. –
이진 검색은 인덱스 s.t를 찾는다. i 번째 비트는 설정되고 i + 1 번째 비트는 설정되지 않습니다. 첫 번째 비트가 설정되지 않고 마지막 비트가 설정되고 완료되었다는 특수한 경우를 추가하십시오.
비트 스트림을 선형 적으로 트래버스하려면 32 비트 청크로 처리하고 비트 AND 0xFFFFFFFF (모두 1)로 변경하고 이에 따라 카운트를 업데이트하십시오.
이것은 최신 CPU가 일반적으로 32 비트 단어에 대해 비트 단위 작업을 단일 원자 작업으로 수행 할 수 있다는 사실을 이용합니다.
AND 결과가 0xFFFFFFFF이면 잠재적으로 더 많은 비트가 있으므로 다음 32 비트 단어를 검사해야합니다. 그렇지 않으면 카운터를 증가시키고 루핑을 중단하십시오.
첫 번째 32 비트 청크 ('x')가 _isn't_'0xFFFFFFFF'가 아니라면 ('~ x + 1') 마지막 하나만 설정됩니다. 나머지 1의 수를 계산하는 데 도움이되지 않을 수도 있습니다. –
모두 1이 아닌 첫 번째 32 비트 청크의 경우 AND 연산은 마지막 1 개가 아닌 1을 설정 한 결과 (예 : 0xFFFFFFFE)를 반환 할 수 있습니다 그런 다음 1의 수를 명시 적으로 계산하거나 룩업 테이블을 사용하여이 최종 청크의 수를 결정할 수 있습니다. – Adamski
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn 'count + = MultiplyDeBruijnBitPosition2 ((~ x + 1) * 0x077CB531U) >> 27]'비트를 계산하는 데는 단지 6 옵시이다. 마지막에, 가지가 없네. –
스트림의 전체 길이를 알고 있으며 임의로 액세스 할 수 있습니까? 1과 0 부분이 비어 있지 않음을 보증합니까? – Patrick87
당신은 이것이 인터뷰 질문이라고 말했습니다 ... 이론적 인 방향 (큰 0 알고리즘 크기 등)이나 구현 중 하나 (캐싱 및 프로세서 아키텍처와 같은 실제 메커니즘의 효율적인 사용)에서 접근 했습니까? –
'0'이후에는 더 이상 '1'을 가질 수 없다는 것을 안다면 간격의 배가됩니다. 이 경우 각 기호를 개별적으로 (또는 작게는 32 비트 또는 64 비트와 같은 그룹으로) 확인해야합니다. – vsz