剑指offer刷题总结(一)位运算

1. 二进制中1的个数

题目描述：

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

代码实现：

/**
 * @ClassName Main
 * @Description TODO
 * @Author 倪然
 * @Date 2019/7/31 15:28
 * Version 1.0
 **/
public class Main {

    /**
     * n&(n-1)能将n的二进制形式最靠近右边的1变为0
     * @param n
     * @return
     */
    public static int method1(int n) {
        int count = 0;
        while(n!=0)
        {
            n = n&(n-1);
            count++;
        }
        return count;

    }

    /**
     * 每次循环判断最低位是否为1，然后将n右移一位
     * @param n
     * @return
     */
    public static int method2(int n) {
        int count=0;
        while(n!=0){
            count+=n&1;
            n>>>=1;
        }
        return count;
    }

    /**
     * temp每次乘2表示二进制每次左移一位
     * @param n
     * @return
     */
    public static int method3(int n){
        int count = 0;
    	long temp = 1;
    	for(int i = 1; i <= 32;i++){
    		if((n&temp) > 0)
    			count++;
    		temp <<=1;
    		// temp*=2;

    	}
        return count;
    }
    public static void main(String [] args) {
        System.out.println(method1(6));
        System.out.println(method2(6));
        System.out.println(method3(6));
    }
}

2. 判断二进制中0的个数

题目描述：

输入一个整数，输出该数二进制表示中0的个数。其中负数用补码表示。

代码实现：

public class problem2 {
    public static int findZero(int n) {
        int count = 0;
        while(n != 0) {
            if((n&1)!=1)
                count++;
            n>>>=1;
        }
        return count;
    }
    public static void main(String [] args) {
        System.out.println(findZero(6));
    }
}

3. 二进制高位连续0的个数

题目描述：

输入一个整数，输出该数二进制高位连续0的个数。其中负数用补码表示。

思路：

每次与最高位为1的二进制进行&操作。0x80000000的二进制是1000 0000 0000 0000 …共32位，最高位为1.

代码实现：

public class problem3 {
    /**
     * 每次与最高位为1的二进制进行&操作
     * 0x80000000的二进制是1000 0000 0000 0000 ...共32位，最高位为1.
     * @param number
     * @return
     */
    public static int numberOfLeadingZeros0(int number){
        if(number == 0)
            return 32;
        int n = 0;
        int mask = 0x80000000;
        int j = number & mask;
        while(j == 0){
            n++;
            number <<= 1;
            j = number & mask;
        }
        return n;
    }

    public static void main(String [] args){
        System.out.println(numberOfLeadingZeros0(1));
    }
}