수학 함수 나 로그 함수없이 숫자가 2의 거듭 제곱인지 확인

수학 함수 나 로그 함수없이 숫자가 2의 거듭 제곱인지 확인

---

사용자가 입력 한 숫자가 2의 거듭 제곱인지 확인하고 싶습니다.

내 코드가 작동하지 않습니다.

public class power_of_two
{  
    public static void main(String args[])  
    {  

        Scanner in=new Scanner(System.in);
        System.out.println("Enter the number : ");
        int num = in.nextInt();

        int other = 1;  
        if(((~num) & 1) == 1)  
        {  
            System.out.println("The number is a power of two");  
        }  
        else  
        {
            System.out.println("The number is a  NOT A power of two");  
        }
    }  
} 

두 수의 거듭 제곱을 어떻게 찾을 수 있는지 알려주세요.
예를 들어 8은 2의 거듭 제곱입니다.
22는 2의 거듭 제곱 이 아닙니다 .

---

양의 정수 n가 2의 거듭 제곱 인지 테스트 할 수 있습니다.

(n & (n - 1)) == 0

n비 양성 (예 : 음수 또는 0)이 될 수있는 경우 다음을 사용해야합니다.

(n > 0) && ((n & (n - 1)) == 0)

---

n진정으로 2의 거듭 제곱 인 경우 이진법은 다음과 같습니다.

10000000...

그래서 이렇게 n - 1보인다

01111111...

그리고 우리가 비트와 그것들을 할 때 :

  10000000...
& 01111111...
  -----------
  00000000...

이제 2의 거듭 제곱 n 이 아닌 경우 이진 표현에는 선행 1 외에 다른 1이 있습니다. 즉, n및 둘 다 n - 1동일한 선행 1 비트를 갖게됩니다 (1을 빼면이 비트를 끌 수 없기 때문에 이진 표현 어딘가에 또 다른 1이 있습니다). 따라서, &동작 생성 할 수 0있으면 n되기 때문에, 2의 누승이 아닌 &두 선두 비트를 보내고 n및 n - 1생산할 예정 1그 자체. 이것은 물론 그것이 n긍정적 이라고 가정합니다 .

이것은 또한 Wikipedia의 "양수가 2의 거듭 제곱인지 확인하는 빠른 알고리즘"에 설명되어 있습니다.

---

빠른 온 전성 검사 :

for (int i = 1; i <= 100; i++) {
    if ((i & (i - 1)) == 0)
        System.out.println(i);
}

1
2
4
8
16
32
64

---

다음을 사용할 수 있습니다 bitwise AND (&) operator.

return (num & -num) == num

이것이 작동하는 이유는 무엇입니까?

숫자 8을 고려하십시오. 이진수는 무엇입니까 (32 비트라고 가정)?

0000 0000 0000 0000 0000 0000 0000 1000

이제 -8이 어떻게 표현되는지 봅시다. ¹

1111 1111 1111 1111 1111 1111 1111 1000

마지막으로 .. 계산해 봅시다 8 & -8.

0000 0000 0000 0000 0000 0000 0000 1000   8
↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓   &
1111 1111 1111 1111 1111 1111 1111 1000  -8
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 1000   8    ¯\_(ツ)_/¯

이제 2의 거듭 제곱 7이 아닌 다른 예를 들어 보겠습니다 .

0000 0000 0000 0000 0000 0000 0000 0111   7
↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓   &                       
1111 1111 1111 1111 1111 1111 1111 1001  -7
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0001  != 7  ¯\_(ة_ة)_/¯

@arshajii가 언급했듯이, num0 이면 어떤 일이 일어날 지 생각해보십시오 .. 해결책을 남겨 드리겠습니다. :)

¹ 그것을 계산하는 방법을 기억하는 좋은 방법 : 보이는 각 0에 대해 가장 오른쪽 비트부터 시작하여 변경하지 마십시오. 1이 표시되면 그대로두고 진행하되 이제부터는 모든 비트를 반전하십시오. 나는 이것을 여기서 더 설명하려고 노력했다 .

---

double input = 22;

while(((input != 2) && input % 2 == 0) || input == 1) {
 input = input /2;
}

return input == 2;

1 또는 홀수에 도달 할 때까지 계속 2로 나눕니다. 1에 도달하면 2의 거듭 제곱이고 그렇지 않으면 그렇지 않습니다.

---

간단한 솔루션 :

bool isPowerOfTwo(int n) {
    // All values < 1 cannot be (positive, at least) powers of two.
    if (n < 1) return false;

    // Keep shifting bits.
    while (n > 1) {
        // Since n > 1, the low bit set means at least two bits must
        // be set, making n no longer a power of two.
        if (n & 0x1) return false;
        // Throw away the bottom (zero) bit.
        n >>= 1;
    }
    // Only one bit was set, therefore, n is a power of two.
    return true;
}

Of course, this is not as optimal as some of the other bit-trickery solutions (which are indeed quite clever), but it's very easy to see how it works, and verify it works in your head.

For the input 4, we get:

n = 4 (0x100)
run loop
n = 2 (0x10)
run loop
n = 1 (0x1)
return true

For an invalid input, like 5, we get:

n = 5 (0x101)
return false (0x101 & 0x1 => 0x1, which is truthy)

---

   public boolean isPowerOfTwo(int n){

            boolean isPower=false;
            int temp=n;

            while(temp>=2){
                if(temp%2==0){
                    isPower=true;

                }else{
                    isPower=false;
                    break;
                }
                temp=temp/2;
            }

            if(isPower){
                System.out.println("power of 2");
            }else{
                System.out.println("not power of 2");
            }

            return isPower;
        }

---

A very simple solution.

int n = 8; // any integer and you can take it from user also
for(;n>0;n++){
    if(n%2 != 0) {
        System.out.println("not a power of two")
        return;
    } // if ends here
    n = n/2;
}// for ends here
System.out.println("power of two")

참고URL : https://stackoverflow.com/questions/19383248/find-if-a-number-is-a-power-of-two-without-math-function-or-log-function