비트 수는

Question

나는

N 요소의 비는 하늘의 배열 A는 진수 표현을 인터뷰 중 하나에서 다음과 같은 질문을 진행하는 방법을 전혀 인식하지 못하고 이대로 PLZ를 해결하기 위해 나에게 몇 가지 아이디어를하는 데 도움이 포함되어있어 음이 아닌 정수 K의 A, 즉 A의 각 원소는 구간 [0; 함수는 -1에 돌아 1로 설정된 비트 수가 10,000,000을 넘으면 K.의 이진 표현에서 1로 설정된 비트 수를 돌려

int bitcount_in_big_octal(const vector<int> &A); 

: 7]

함수를 작성한다.

배열이 매우 클 수 있다고 가정하십시오.

N은 [1..100,000] 범위의 정수라고 가정합니다.

Answer 1

시간 제한이 있습니까? 하나의 아이디어가 있습니다. 먼저 다음 사전을 작성하십시오. {0-> 0, 1-> 1,2-> 1, 3-> 2, 4-> 1, 5-> 1, 6-> 2, 7-> 3}. 그런 다음 배열 A를 반복하여 사전을 사용하여 모든 요소에서 1을 합합니다. 당신의 표현

이상

Answer 2

1. 반복 처리를 위해-각이 반복 처리에서 요소의 비트의 숫자로 표현을 변환합니다. @ meteorgan의 대답은이를 수행하는 가장 좋은 방법입니다. 비트 수 이외의 표현을 필요로하는 경우, 다른 어떤 용도로든 사용할 수있는 중간 형식으로 변환하고 싶을 것입니다. byte[] : 표현의 각 옥텟은 하나의 byte과 일치해야하며, 자바의 바이트가 서명 된 것은 중요하지 않습니다. 다음에 대한-각 배열의 byte, lib을 계산 기존의 비트를 사용 int에 byte 캐스트 등, 자신을 Integer.bitCount(...)를 사용하거나 롤 - 탈출, 비트를 계산
2. 실행중인 총에 결과를 추가 당신이 당신의 문턱을 치면 반복.

세부 사항 (예 : 연결 한 라이브러리)과 같은 Java 응답이지만 C++의 알고리즘 단계는 대체 라이브러리를 찾거나 사전 응답을 사용합니다.

Answer 3

다음은 인덱싱 된 (사전) 기반 방식을 사용하는 솔루션입니다.

INDEX = [0, 1, 1, 2, 1, 2, 2, 3] 

def bitcount_in_big_octal(A): 
    counter = 0 
    for octal in A: counter += INDEX[octal] 
    return counter