[C#] 숫자가 2의 거듭 제곱인지 확인하는 방법

오늘 저는 숫자가 2의 거듭 제곱인지 확인하는 간단한 알고리즘이 필요했습니다.

알고리즘은 다음과 같아야합니다.

단순한
모든 ulong값을 정정하십시오 .

이 간단한 알고리즘을 생각해 냈습니다.

private bool IsPowerOfTwo(ulong number)
{
    if (number == 0)
        return false;

    for (ulong power = 1; power > 0; power = power << 1)
    {
        // This for loop used shifting for powers of 2, meaning
        // that the value will become 0 after the last shift
        // (from binary 1000...0000 to 0000...0000) then, the 'for'
        // loop will break out.

        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}

그러나 나는 정확히 둥근 숫자인지 확인하는 방법에 대해 생각했습니다 . 그러나 2 ^ 63 + 1을 확인하면 반올림으로 인해 정확히 63을 반환했습니다. 따라서 2의 거듭 제곱 63이 원래 숫자와 같은지 확인했습니다. 계산은 정확한 숫자가 아닌 s 로 수행되기 때문 입니다.log₂ xMath.Logdouble

private bool IsPowerOfTwo_2(ulong number)
{
    double log = Math.Log(number, 2);
    double pow = Math.Pow(2, Math.Round(log));
    return pow == number;
}

true주어진 잘못된 값으로 돌아 왔습니다 : 9223372036854775809.

더 나은 알고리즘이 있습니까?

답변

이 문제에 대한 간단한 트릭이 있습니다.

bool IsPowerOfTwo(ulong x)
{
    return (x & (x - 1)) == 0;
}

이 함수는 의 거듭 제곱이 아닌에 true대해 보고 합니다 . 제외하려면 다음과 같이하십시오.02

bool IsPowerOfTwo(ulong x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}

설명

가장 먼저 MSDN 정의의 비트 이진 및 연산자 :

이항 및 연산자는 정수 유형 및 부울에 대해 사전 정의됩니다. 정수 유형의 경우 &는 피연산자의 논리 비트 AND를 계산합니다. 부울 피연산자의 경우 &는 피연산자의 논리 AND를 계산합니다. 즉, 두 피연산자가 모두 참인 경우에만 결과가 참입니다.

이제이 모든 것이 어떻게 작동하는지 살펴 보겠습니다.

이 함수는 부울 (true / false)을 반환하고 unsigned long 유형 (이 경우 x)의 수신 매개 변수 하나를 허용합니다. 단순화를 위해 누군가가 값 4를 전달하고 다음과 같이 함수를 호출했다고 가정합니다.

bool b = IsPowerOfTwo(4)

이제 x의 각 항목을 4로 바꿉니다.

return (4 != 0) && ((4 & (4-1)) == 0);

글쎄, 우리는 이미 4! = 0이 참으로 사라지는 것을 알고있다. 그러나 어떻습니까 :

((4 & (4-1)) == 0)

이것은 물론 이것으로 번역됩니다.

((4 & 3) == 0)

그러나 정확히 무엇 4&3입니까?

4의 이진 표현은 100이고 3의 이진 표현은 011입니다 (&는이 숫자의 이진 표현을 기억합니다). 그래서 우리는 :

100 = 4
011 = 3

이 값들이 기본 덧셈과 매우 유사하게 쌓여 있다고 상상해보십시오. &연산자, 그렇지 않으면 0이다 따라서, 두 값이 모두 1과 같으면, 결과가 1 인 것을 말한다 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0, 및 0 & 1 = 0. 그래서 우리는 수학을합니다 :

100
011
----
000

결과는 단순히 0입니다. 다시 돌아가서 return 문이 무엇을 의미하는지 살펴 보겠습니다.

return (4 != 0) && ((4 & 3) == 0);

이제 다음과 같이 번역됩니다.

return true && (0 == 0);

return true && true;

우리는 모두 그것이 true && true간단 하다는 것을 알고 있으며 true, 이것은 예에서 4가 2의 거듭 제곱임을 보여줍니다.

답변

이것과 다른 비트 트위들 링 해킹을 문서화하고 설명하는 일부 사이트는 다음과 같습니다.

그리고 그들의 할아버지, Henry Warren, Jr.의 “Hacker ‘s Delight”책 :

http://www.hackersdelight.org/

Sean Anderson의 페이지에서 설명하는 것처럼 이 표현 ((x & (x - 1)) == 0)은 0이 2의 거듭 제곱임을 잘못 표시합니다.

(!(x & (x - 1)) && x)

그 문제를 해결하기 위해.

답변

return (i & -i) == i

답변

bool IsPowerOfTwo(ulong x)
{
    return x > 0 && (x & (x - 1)) == 0;
}

답변

최근에 http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/ 에 대한 기사를 썼습니다 . 비트 카운팅, 로그를 올바르게 사용하는 방법, 클래식 “x &&! (x & (x-1))”확인 및 기타 사항을 다룹니다.

답변

간단한 C ++ 솔루션 은 다음과 같습니다 .

bool IsPowerOfTwo( unsigned int i )
{
    return std::bitset<32>(i).count() == 1;
}

답변

허용되는 답변에 대한 다음 부록은 일부 사람들에게 유용 할 수 있습니다.

2의 거듭 제곱은 이진수로 표현 될 때 항상 1 처럼 보이고 n이 0 보다 크거나 같은 n 제로 가 옵니다 . 예 :

Decimal  Binary
1        1     (1 followed by 0 zero)
2        10    (1 followed by 1 zero)
4        100   (1 followed by 2 zeroes)
8        1000  (1 followed by 3 zeroes)
.        .
.        .
.        .

등등.

1이러한 종류의 숫자에서 빼면 0이되고 n이 되고 다시 n이 위와 같습니다. 전의:

Decimal    Binary
1 - 1 = 0  0    (0 followed by 0 one)
2 - 1 = 1  01   (0 followed by 1 one)
4 - 1 = 3  011  (0 followed by 2 ones)
8 - 1 = 7  0111 (0 followed by 3 ones)
.          .
.          .
.          .

등등.

요점에 오기

우리가 x2의 거듭 제곱 인 숫자의 비트 AND를 수행하면 어떻게됩니까 x - 1?

하나는 x0으로 정렬 x - 1되고 모든 0은 x1로 정렬되어 x - 1비트 AND가 0이됩니다. 그리고 위에서 언급 한 단일 행 응답이 올바른 방법입니다.

위의 허용되는 답변의 아름다움에 더 추가-

그래서 우리는 지금 처분 할 재산이 있습니다 :

숫자에서 1을 빼면 이진 표현에서 가장 오른쪽 1이 0이되고 가장 오른쪽 1 이전의 모든 0이 1이됩니다.

이 속성을 가장 잘 사용하는 방법은 다음과 같습니다.- 주어진 숫자의 이진 표현에 몇 개의 1이 있습니까? 주어진 정수에 대해 짧고 달콤한 코드 x는 다음과 같습니다.

byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);

위에서 설명한 개념에서 증명할 수있는 숫자의 또 다른 측면은 “모든 양수를 2의 거듭 제곱의 합으로 나타낼 수 있습니까?”입니다..

예, 모든 양수는 2의 거듭 제곱의 합으로 표현할 수 있습니다. 예 : 숫자를 가져옵니다 117.

The binary representation of 117 is 1110101

Because  1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have  117     = 64      + 32     + 16    + 0    + 4   + 0  + 1