하나의 수가 2 인지 아 닌 지 를 판단 하 는 정수 차 멱 - 비트 연산 의 묘 용

하나의 수가 2 인지 아 닌 지 를 판단 하 는 정수 차 멱
제목: 하나의 방법 을 실현 하여 하나의 정수 가 2 의 정수 차 멱 인지 판단 합 니 다 (예 를 들 어 16 은 2 의 4 차방, true 로 돌아 갑 니 다. 18 은 2 의 정수 차 멱 이 아니면 false 로 돌아 갑 니 다).성능 이 가능 한 한 높 아야 한다.
폭력 법

중간 변수 temp 를 만 들 고 초기 값 은 1 입 니 다.그 다음 에 하나의 순환 에 들 어가 매번 순환 할 때마다 temp 와 목 표를 비교 하 게 하고 같 으 면 정수 2 의 정수 차 멱 이다.같 지 않 으 면 temp 를 1 배로 늘 리 고 계속 순환 하 며 비교 합 니 다.temp 의 값 이 목표 정수 보다 클 때 목표 정수 가 2 의 정수 차 멱 이 아니 라 는 것 을 설명 합 니 다.

시간 복잡 도: O (logn)
비트 연산 의 묘 용
단계:

판단 해 야 할 정 수 를 2 진법 으로, 10 진법 의 2 를 2 진법 으로 10B, 4 를 2 진법 으로 100 B, 8 을 2 진법 으로 1000 B 로...

예 를 들 어 하나의 정수 시 2 의 정수 차 멱 은 가장 도착 한 것 을 제외 하고 다른 위 치 는 모두 0 이다.

판단 해 야 할 수 - 1 을 2 급 제로 바 꾸 면 2 진법 의 숫자 가 모두 1 이 된다.

판단 을 기다 리 는 원수 치 와 1 을 뺀 결과 로 위치 와 연산, 즉 n & (n - 1) 을 한다.0 과 1 의 위 치 를 판단 할 수 있 는 결 과 는 0 이다.

판단 해 야 할 수가 2 의 정수 차 멱 과 그 자체 가 1 을 뺀 결과 에 따라 위치 와 연산 을 하면 결 과 는 반드시 0 이다.그렇지 않 으 면 판단 해 야 할 수 는 2 의 정수 차 멱 이 아니다.

하나의 정수 n 에 대해 n & (n - 1) 의 결과 가 0

인지 아 닌 지 를 계산 해 야 한다.

package some_problem;/**
 * Copyright (C), 2019-2020
 * author  candy_chen
 * date   2020/7/20 20:37
 * version 1.0
 * Description:         2     
 */

/**
 *
 */
public class isPowerOf2 {

    /**
     *      O(logn)
     * @param num
     * @return
     */

    public static boolean isPowerOf2_v1(int num){
        int temp = 1;
        while (temp < = num){
            if (temp == num){
                return true;
            }
            temp = temp << 2;  //   2         ，           
        }
        return false;
    }

    /**
     *      O(1)
     *          
     * @param num
     * @return
     */
    public static boolean isPowerOf2(int num){
        return (num & num -1) == 0;
    }
}