바이너리로 변환하지 않고 해밍 무게를 확인하려면 어떻게해야합니까?
-
20-08-2019 - |
문제
어떻게 얻을 수 있습니까? "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
해결책
IMO, 좋은 접근 방식은 조회 테이블을 사용하는 것입니다 - 바이트를 1의 숫자로 변환하는 사전을 만듭니다 (게시 한 코드를 사용하여 생성하면 한 번만 실행하면 필요합니다). 이와 같이:
def number_of_ones(n):
sum = 0
while n != 0:
sum += lookup_table[n & 0xff]
n >>= 8
return sum
나는 이것이 우주와 런타임 사이의 상당히 좋은 상충 관계라고 생각합니다.
다른 팁
나는 파이썬 프로그래머가 아니지만, 당신이 따라갈 수 있기를 바랍니다.
c = 0
while n:
c += 1
n &= n - 1
return c
약간 모호하지만 주요 장점은 속도와 단순성입니다. while 루프는 1에서 1으로 설정할 때마다 한 번만 반복됩니다.
이 계산을 덜 복잡하게 만들 수는 없습니다. 그것은 O (n) 비트 수가 될 것입니다. 또는 Trick의 답이 알 수 있듯이 O (n) 비트의 수는 1으로 설정된 비트 수; 그러나 사용중인 모든 숫자가 특별한 경우가 아니라면 후자는 평균적으로 N/2 여야하므로 O (n) 숫자는 모두 동일합니다.
물론 조회 테이블 트릭은 실제로 계산 복잡성을 위해 아무것도하지 않습니다. 그것은 단지 우주로 시간을 지불하지만 기본 경제를 바꾸지 않고는 각 비트를 한 번 검사해야합니다. 어떻게든 그리고 그 주위에는 방법이 없습니다. 논리적으로, 각각을 검사하지 않고 숫자의 비트에 대한 질문에 답할 수는 없습니다.
파이썬에서는 한 번에 정수를 검사해야하기 때문에이 예 중 많은 예가 실제로 O (n^2)이기 때문에 약간 조잡하다고 생각합니다. , a + 또는 an & 또는 a / 작업은 각 바이트를 적어도 한 번 보며, 숫자가 0으로 줄어들 때까지 반복해서 발생합니다 (위의 계획에서). n^2) 운영. Python이 여기서 진정한 O (N) 솔루션을 허용 할 것이라고 확신하지 않습니다.
어쨌든 : 당신이 정말로 묻고 있다면 계산 특히 Big-O 분석을 의미하는 복잡성은 귀하의 답입니다. :-)
한 줄로하려면 다음을 수행 할 수 있습니다.
sum( [x&(1<<i)>0 for i in range(32)] )
여기:
def bitcount (int_no) :
c = 0
while(int_no):
int_no &= (int_no - 1)
c += 1
return c
이것은 원래 C에서 구현 된 오래되고 효율적인 방법 일 수 있습니다 (Algo는 기억할 수없는 이름이 있습니다). 그것은 나에게 잘 작동합니다.
p = lambda n : n 및 1+p (n & (n-1))
이것은 단락 및 재귀를 사용합니다. N이 0보다 클 때 전환하면 1+P (N & (N-1))를 계산하여 P (N & (N-1))이 호출되는 등 N이 0 일 때. 그것은 0을 반환합니다. 복잡성은 O (n) 이진에 존재하는 횟수를 실행하기 때문에 복잡성입니다.
예 : p (9) = 1+p (8) = 1+1+p (0) = 1+1+0 = 2