이 비트 단위 연산은 2의 거듭제곱을 어떻게 확인합니까?

이 비트 단위 연산은 2의 거듭제곱을 어떻게 확인합니까?

저는 사소한 코드를 보고 있습니다.하지만 제 수학은 형편없이 실패했어요.

다음은 다음을 사용하여 2의 거듭제곱 여부를 확인하는 조건입니다.

if((num != 1) && (num & (num - 1))) { /* make num pow of 2 */ }

질문입니다. num과 num - 1 사이의 비트 AND를 사용하면 숫자가 2의 거듭제곱인지 어떻게 알 수 있을까요?

2 빼기 1의 거듭제곱은 모두 1입니다. (2 ^N - 1 = 111....b)

2 = 2^1.  2-1 = 1 (1b)
4 = 2^2.  4-1 = 3 (11b)
8 = 2^3.  8-1 = 7 (111b)

8을 예로 들어보자.1000 & 0111 = 0000

따라서 이 식은 숫자가 2의 거듭제곱이 아닌지를 테스트합니다.

첫 번째 경우 2 == 1을 확인합니다⁰.

다른 경우에는num & (num - 1)도입:

즉, 임의의 숫자를 취하여 낮은 쪽의 비트를 마스크하면 다음 두 가지 경우 중 하나를 얻을 수 있습니다.

1. 이 숫자가 이미 2의 거듭제곱인 경우, 1보다 작으면 하위 비트만 설정된 이진수가 됩니다.사용.&아무 것도 안 할 거야

   • 8의 예:0100 & (0100 - 1)-->(0100 & 0011)-->0000

2. 이 숫자가 이미2의 거듭제곱이 아닌 경우, 1이 가장 높은 비트에 닿지 않기 때문에 그 결과는 적어도 2가 num보다 작은 최대제곱이 됩니다.

   • 3의 예:0011 & (0011 - 1)-->(0011 & 0010)-->0010

   • 13의 예:1101 & (1101 - 1)-->(1101 & 1100)-->1100

따라서 실제 표현식은 2를 포함하여⁰ 2의 거듭제곱이 아닌 모든 것을 찾습니다.

나는 두 가지 보완에 의존하는 이 접근방식을 선호한다.

bool checkPowTwo(int x){
    return (x & -x) == x;
}

음.

X = 1000이면 x-1 = 0111입니다.1000 & 0111은 0000 입니다.

2의 거듭제곱인 각 숫자 X에는 x-1이 있고 위치 x에 1이 0이 있습니다.그리고 0과 1의 비트는 항상 0입니다.

숫자 x가 2의 거듭제곱이 아닌 경우(예: 0110).x-1은 0101이고,는 0100입니다.

0000 - 1111 내의 모든 조합은 다음과 같습니다.

   X  X-1 X && X-1  
0000 1111 0000   
0001 0000 0000 
0010 0001 0000
0011 0010 0010
0100 0011 0000
0101 0100 0100
0110 0101 0100
0111 0110 0110
1000 0111 0000
1001 1000 1000
1010 1001 1000
1011 1010 1010
1100 1011 1000
1101 1100 1100
1110 1101 1100
1111 1110 1110

그리고 1에 대해서는 별도 체크가 필요 없습니다.

n이 소정의 수치라고 가정합니다.n이 2의 거듭제곱(n & !&!(n & (n-1))일 경우 1을 반환하고 그렇지 않을 경우 0을 반환합니다.

정수가 2의 거듭제곱인지 아닌지를 결정합니다.한다면(x & (x-1))0이 되면 숫자는 2의 거듭제곱이 됩니다.

예를 들어,x여덟 살이다1000바이너리);x-1= 7 (0111).

if    1000
  &   0111
---------------
      0000

시연하는 C 프로그램:

#include <stdio.h>

void main()
{
    int a = 8;
    if ((a&(a-1))==0)
    {
        printf("the bit is power of 2  \n");
    }
    else 
    {
        printf("the bit is not power of 2\n");
    }
}

이 출력은the bit is power of 2.

#include <stdio.h>

void main()
{
    int a = 7;
    if ((a&(a-1))==0)
    {
        printf("the bit is power of 2  \n");
    }
    else 
    {
        printf("the bit is not power of 2\n");
    }
}

이 출력은the bit is not power of 2.

여기에 친절하게 설명하다

또한 0을 2의 거듭제곱으로 간주합니다.그 용도를 수정하려면!(x & (x - 1)) && x;대신.

양의 정수를 1씩 줄이는 경우:

1. 이면 0이 되고, 0이면 0이 되고, 0이면 0이 됩니다.-1.
2. 비트가 「」인 .1는 '비트로 0, 다른 비트는 변경되지 않습니다.
3. 않으면 모든 하위 인 "" " " " " " " " "」0가 「비트로 」로 설정되어 있습니다.1 가장 '''는''자''자'자1(「」로 되어 있는 )0, 다른 비트는 변경되지 않습니다.

1: 이 1 1 1:x & (x - 1)0, 아직, 아직, 갱신되지 않았다x는 2의 거듭제곱이 아니라 단순한 카운터 예시입니다.

와 3: '2'가 3인 경우:x ★★★★★★★★★★★★★★★★★」x-1공통 비트는 없습니다.이것은 위의 두 경우 모두 다른 비트가 모두0임을 의미하기 때문에 숫자는 1비트를 가지므로 2의 거듭제곱이 됩니다.

ifx는 부호 경우 감소 2개의 보수로 하지 않습니다.x ★★★★★★★★★★★★★★★★★」x-1적어도 공통의 부호 비트를 가지고 있다는 건x & (x-1)0으로 하다

2의 거듭제곱을 테스트하려면 다음 코드가 필요합니다.

int is_power_of_2(unsigned x) {
    return x && !(x & (x - 1));
}

#include <stdio.h>
void powerof2(int a);
int a;

int main()
{
    while(1)
    {
       printf("Enter any no. and Check  whether no is power of 2 or no \n");
       scanf("%d",&a);
       powerof2(a);
    }
}
void powerof2(int a)
{
    int count = 0;
    int b=0;
   while(a)
   {
     b=a%2;
     a=a/2;
     if(b == 1)
        {  count++;  }
   }
  if(count == 1)
   {
      printf("power of 2\n");
   }
  else
    printf("not power of 2\n");
}

C의 다음 프로그램은 숫자가 2의 거듭제곱인지 아닌지를 확인하고 2의 거듭제곱인 숫자도 찾습니다.

#include<stdio.h>
void main(void)
{
    unsigned int a;
    unsigned int count=0
    unsigned int check=1;
    unsigned int position=0;
    unsigned int temp;
    //get value of a
    for(i=0;i<sizeof(int)*8;i++)//no of bits depend on size of integer on that machine
    {
        temp = a&(check << i);
        if(temp)
        {
            position = i;
            count++;
        }
    }
    if(count == 1)
    {
        printf("%d is 2 to the power of %d",a,position);
    }
    else
    {
        printf("Not a power of 2");
    }
}

다른 방법이 있습니다.- 숫자가 2의 거듭제곱인 경우 1비트만 이진 형식으로 설정됩니다.

예를 들어 8은 0x1000에 해당하고 여기서 1을 빼면 0x0111이 됩니다.

원래 번호(0x1000)의 종료 조작은 0이 됩니다.

만약 그렇다면, 숫자는 2의 거듭제곱이다.

    void IsPowerof2(int i)
    {
    if(!((i-1)&1))
    {
    printf("%d" is a power of 2, i);
    }
    }

다른 방법은 다음과 같습니다.-

만약 우리가 2의 거듭제곱인 숫자의 덧셈을 취한다면,

예를 들어, 8개의 0x1000을 보완하면 0x0111을 얻고 1을 더하면,

같은 수, 만약 그렇다면 그 수는 2의 거듭제곱이다

    void IsPowerof2(int i)
    {
    if(((~1+1)&i) == 1)
    {
    printf("%d" is a power of 2,i):
    }
    }                                                     

언급URL : https://stackoverflow.com/questions/1053582/how-does-this-bitwise-operation-check-for-a-power-of-2