바이너리로 변환하지 않고 해밍 무게를 어떻게 확인할 수 있습니까?

Question

"1"의 숫자을 실제로 변환 및 계산하지 않고 숫자의 이진 표현으로 가져올 수 있습니까?

def number_of_ones(n): 
     # do something 
     # I want to MAKE this FASTER (computationally less complex). 
     c = 0 
     while n: 
     c += n%2 
     n /= 2 
     return c 


>>> number_of_ones(5) 
    2 
>>> number_of_ones(4) 
    1 

Answer 1

IMO, 좋은 방법은 룩업 테이블을 사용하는 것입니다. 바이트를 1의 수로 변환하는 사전을 만듭니다. 생성 한 코드를 사용하면 한 번만 실행하면됩니다. 다음과 같은 것을 사용하십시오 :

def number_of_ones(n): 
    sum = 0 
    while n != 0: 
     sum += lookup_table[n & 0xff] 
     n >>= 8 
    return sum 

저는 이것이 공간과 실행 시간 사이에 상당히 좋은 절충이라고 생각합니다. 단일 라인에서 그것을하고 싶은 경우

Answer 2

나는 파이썬 프로그래머가 아니지만 잘하면 충분히 따라갈 수 있습니다.

c = 0 
while n: 
    c += 1 
    n &= n - 1 

return c 

약간은 분명하지만 속도와 단순성이 가장 큰 장점입니다. while 루프는 n의 1로 설정된 모든 비트에 대해 한 번만 반복됩니다.

Answer 3

실제로 속도가 걱정된다면 C로 코딩하고 (방법은 this question 참조), ctypes과 같은 것을 사용하여 C 구현체와 인터페이스하십시오.

Answer 4

, 당신은 사용할 수 있습니다

sum([x&(1<<i)>0 for i in range(32)]) 

Answer 5

당신이 계산 덜 복잡 할 수 없습니다. & 트릭이 표시된 대답과 같이 O (n) 비트 수 또는 O (n) 비트 수를 1로 설정합니다. 그러나 사용하고있는 모든 숫자가 특별한 경우가 아니면, 후자는 평균 n/2가되어야합니다. 따라서 두 O (n) 숫자는 동일합니다.

물론 조회 테이블 트릭은 실제로 계산상의 복잡성에 대해 아무 것도하지 않습니다. 그것은 단지 공간을 가지고 시간을 지불하는 것입니다. 근본적인 경제를 바꾸지 않고, 당신은 각 비트를 한번 검사해야만합니다. 어떻게 든 그리고 그 주위에 방법이 없습니다. 논리적으로는 숫자를 조사하지 않고 숫자의 비트에 대한 질문에 논리적으로 대답 할 수 없습니다.

이제 파이썬에서 전체 숫자를 한 번에 검사해야하므로이 예제 중 많은 수가 실제로 O (n^2)이기 때문에 약간 엉터리라고 생각합니다. 100 바이트, a + 또는 & 또는 a/연산은 각 바이트를 적어도 한 번 살펴볼 것입니다. 그리고 숫자가 0으로 줄어들 때까지 반복적으로 발생합니다 (위에서 설명한 스키마에서) 정말로 O (n^2) 작업입니다. 파이썬이 진정한 O (n) 솔루션을 허용 할 지 모르겠습니다.

어쨌든 : computational 복잡성, 특히 빅 O 분석을 의미하는 질문은 그 답입니다. :-)

Answer 6

p = 람다 N : N이고, 1 + P (N &는 (N-1))

n은 0보다 큰 경우는, 단락과 재귀를 사용되면 1을 계산하도록 스위치 p (n & (n-1)) 여기서 p (n & (n-1))를 호출하면 n이 0 일 때 0을 반환합니다. 복잡도는 O 1의 수가 2 진수에 존재합니다.

예 : P (9) = 1 + P (8) = 1 + 1 + P (0) = 여기서 1 + 1 + 0 = 2

Answer 7

:

DEF bitCount (int_no)

c = 0 
while(int_no): 
    int_no &= (int_no - 1) 
    c += 1 
return c 

이

원래 (너 한테 내가 기억할 수있는 이름을 가진) C에 위해 구현이 작업을 수행 할 수있는 오래되고 효율적인 방법 ... 수 있습니다. 그것은 나를 위해 잘 작동합니다 다른 사람을위한 희망