C에서 임의로 큰 양의 정수를 계산하는 비트 #

Question

거기에는 많은 계산 방법이 있지만 내 경우에는 임의로 큰 숫자에 최대 두 세트의 비트가 포함되어 있는지 테스트해야합니다.

저는 작업을 수행하는 매우 빠른 것으로 보이는 다음 함수를 작성했지만 C#으로 더욱 최적화 될 수 있는지 알아보고 싶었습니다. 이 함수는 몇 백만 번 루프에서 호출됩니다. 중요

public static byte [] BitCountLookupArray = new byte [] 
{ 
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 
}; 

// The parameter [number] will NEVER be negative. 
public static bool HasSetBitCountOfLessThenThree (System.Numerics.BigInteger number) 
{ 
    int sum = 0; 
    byte [] bytes = null; 

    bytes = number.ToByteArray(); 

    for (int i=0; i < bytes.Length; i++) 
    { 
     sum += BitCountLookupArray [bytes [i]]; 
    } 

    return (sum < 3); 
} 

: 인자 [번호] 함수는 전송 NEVER는 제외 할 것이다. 내가 생각

어떤 점이었다 :

• 함수가 정적 만들기. 끝난.
• 정적 조회 배열 사용. 끝난.
• 바이트 수는 종종 100,000을 넘기 때문에 배열 색인 대신 포인터를 사용합니다. 이것이 얼마나 도움이 될지 확신하지 못합니다.
• .NET에서 슬프게도 보장 할 수없는 인라인 함수를 강제 적용합니다.

다른 제안 사항이 있습니다. 당신이 최적화 할 수 있습니다

Answer 1

이 방법이 더

가장 확실한 최적화는 그 시점 과거의 더 일치하는 비 물질적이기 때문에, 즉시 sum == 3로 루프를 중퇴하는 것입니다

for (int i=0; i < bytes.Length; i++) 
{ 
    sum += BitCountLookupArray [bytes [i]]; 
    if(sum >= 3) 
    { 
     return false // This will stop the execution of unnecessary lines 
         // as we need to know whether sum is less than 3 or not.       
    } 
} 

return true; 

Answer 2

.

bytes을 두 번 설정할 필요가 없습니다. 간단하게 byte [] bytes = number.ToByteArray();을 사용하십시오, 그러나 여기에있는 장점은 아주 작습니다. 당신은 단지 당신 미만 3 세트 비트가 있는지 여부를 알 필요가 있기 때문에

Answer 3

, 나는 이것을 제안 :

// remove two bits 
number &= number - 1; 
number &= number - 1; 
// if number != 0, then there were 3 or more bits set 
return number.IsZero; 

물론 비의 방법도 작동하고, 나는 전략이 빠를 것이다 모르겠어요.

대안 :

//remove one bit 
number &= number - 1; 
// if the number of bits left is 0 or 1, there were < 3 bits set 
return number.IsZero || number.IsPowerOfTwo; 

먼저 테스트하고, 잠시 후 제거 아마 더 빠르다 :

return number.IsZero ||  // zero bits? 
    number.IsPowerOfTwo ||  // one bit? 
    (number & (number - 1)).IsPowerOfTwo; // two bits?