Python은 Bit Twiddling Hacks의 C 코드와 동일합니까?

Question

가능한 한 빨리 만들려고 시도하는 방법이 있습니다. 나는 Bit Twiddling Hacks에서 아래의 알고리즘을 시도하고 싶지만, C는 무엇인지 모르겠습니다. 'type T'는 무엇이고 파이썬은 (T) ~ (T) 0/3에 해당하는 것은 무엇입니까?

( 타입 T에 의해 파라미터) 128 개까지 비트 폭의 정수 가장 비트 계산 방법의 일반화이있다 :

v = v - ((v >> 1) & (T)~(T)0/3);  // temp 
v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);  // temp 
v = (v + (v >> 4)) & (T)~(T)0/255*15;      // temp 
c = (T)(v * ((T)~(T)0/255)) >> (sizeof(v) - 1) * CHAR_BIT; // count 

Answer 1

T가 정수형 인 서명하지 않았다고 가정합니다. 이것은 C이므로 8, 16, 32, 64 또는 128 중 하나 일 가능성이 있습니다 (반드시 그런 것은 아닙니다). 코드 샘플에 반복적으로 나타나는 조각 (T)~(T)0은 값 2 ** N-1을 제공합니다 여기서 N은 T 타입의 너비입니다. 코드에서 N이 올바른 연산을 위해 8의 배수 여야한다고 생각합니다.

다음은 주어진 코드를 Python으로 직접 변환 한 것으로, T로 비트의 너비를 N으로 매개 변수화했습니다.

def count_set_bits(v, N=128): 
    mask = (1 << N) - 1 

    v = v - ((v >> 1) & mask//3) 
    v = (v & mask//15*3) + ((v >> 2) & mask//15*3) 
    v = (v + (v >> 4)) & mask//255*15 
    return (mask & v * (mask//255)) >> (N//8 - 1) * 8 

주의 사항 :

이

(1) 위의 단지 2 ** 128까지의 번호를 작동합니다. 하지만 더 큰 숫자로 일반화 할 수는 있습니다.

(2) 명백한 비 효율성이 있습니다. 예를 들어 'mask // 15'가 두 번 계산됩니다. 컴파일러가 런타임보다는 컴파일 타임에 거의 확실하게 분할을 수행 할 것이기 때문에 이것은 C에서 중요하지 않지만 파이썬의 훔쳐보기 최적화 기는 그렇게 영리하지 않을 수 있습니다.

(3) 가장 빠른 C 방법은 가장 빠른 Python 방법으로 번역되지 않을 수 있습니다. Python 속도의 경우 Python 비트 연산의 수를 최소화하는 알고리즘을 찾고 있어야합니다. Alexander Gessler가 말했듯이 : 프로파일!

Answer 2

복사 한 내용은 코드를 생성하기위한 템플릿입니다. 이 템플릿을 다른 언어로 번역하지 않고 빠른 실행을 기대하는 것은 좋지 않습니다. 템플릿을 확장합시다.

(T) ~ (T) 0은 "T 유형에 맞는만큼 1 비트"를 의미합니다. 이 알고리즘은 우리가 우리가 관심을 가질만한 다양한 T-크기에 계산됩니다 4 마스크를 필요로한다.

>>> for N in (8, 16, 32, 64, 128): 
...  all_ones = (1 << N) - 1 
...  constants = ' '.join([hex(x) for x in [ 
...   all_ones // 3, 
...   all_ones // 15 * 3, 
...   all_ones // 255 * 15, 
...   all_ones // 255, 
...   ]]) 
...  print N, constants 
... 
8 0x55 0x33 0xf 0x1 
16 0x5555 0x3333 0xf0f 0x101 
32 0x55555555L 0x33333333L 0xf0f0f0fL 0x1010101L 
64 0x5555555555555555L 0x3333333333333333L 0xf0f0f0f0f0f0f0fL 0x101010101010101L 
128 0x55555555555555555555555555555555L 0x33333333333333333333333333333333L 0xf0f0f0f0f0f0f0f0f0f0f0f0f0f0f0fL 0x1010101010101010101010101010101L 
>>> 

당신은 32 비트 경우에 생성 된 마스크는 하드 32 비트에서 일치하는지 알 수 있습니다를 C 코드. 구현 세부 사항 : 32 비트 마스크 (Python 2.x)에서 접미어 L을 잃고 Python 3.x의 모든 접미어 L을 잃습니다.

전체 템플릿과 (T) ~ (T) 0 케이 퍼는 단지 난해한 궤변임을 알 수 있습니다. k 번째 바이트 타입 아주 간단히 말하면, 4 개는 마스크 필요

k bytes each 0x55 
k bytes each 0x33 
k bytes each 0x0f 
k bytes each 0x01 

을 최종 시프트는 단지 (즉 8 * (K-1)) N-8 비트이다. 옆으로 : 템플릿 코드가 CHAR_BIT가 8이 아닌 머신에서 실제로 작동하는지는 의심 스럽지만 요즘에는 그다지 많지 않습니다.

업데이트 : C에서 Python으로 이러한 알고리즘을 음역 할 때 정확성과 속도에 영향을주는 또 다른 사항이 있습니다. C 알고리즘은 종종 부호없는 정수를 가정합니다.C에서 부호없는 정수 연산은 2 ** N을 표준으로합니다. 즉, 최하위 N 비트 만 유지됩니다. 오버플로 예외는 없습니다. 많은 비트 트위 들링 알고리즘이 이것에 의존합니다. 그러나 (a)는 파이썬의 int 및 long (b)는 오래된 파이썬 2.X는 최근 파이썬 2.Xs가 자동으로 intlong에 파이썬 3.x를 int == 파이썬 2.x에서 long을 촉진 예외를 발생합니다 서명됩니다.

정확성 문제는 일반적으로 Python 코드에서 적어도 한 번 register &= all_ones이 필요합니다. 최소한의 올바른 마스킹을 결정하기 위해서는 세심한 분석이 필요합니다.

int 대신 long에서 작업하는 것이 효율성을 크게 향상시키지 않습니다. 32 비트 all_ones가 long이기 때문에 32 비트 알고리즘은 0의 입력에서도 long 답변을 반환한다는 것을 알 수 있습니다.