算法入门第13天

位运算

231. 2 的幂

这题用位运算解法比较简单，也可以用递归啥的

/**
 231. 2 的幂
 给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

 如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。



 示例 1：

 输入：n = 1
 输出：true
 解释：20 = 1
 示例 2：

 输入：n = 16
 输出：true
 解释：24 = 16
 示例 3：

 输入：n = 3
 输出：false
 示例 4：

 输入：n = 4
 输出：true
 示例 5：

 输入：n = 5
 输出：false


 提示：

 -231 <= n <= 231 - 1

 * @author zeroheart
 * @since 2022/4/4
 */
public class Question231 {
    public boolean isPowerOfTwo(int n) {
        // 位运算的特殊解法。4 & 3 = （100 & 011）= 0
        // return (n > 0) && ((n & (n-1)) == 0);

        if(n == 0) return false;
        while (n>0){
            if(n == 1)return true;
            if(n%2!=0) return false;
            n = n / 2;
        }
        return false;
    }

    public static void main(String[] args) {
    }


}

191. 位1的个数

这题和上面的一样，用到了同一个位运算的式子，也有其他方法处理。

n & (n-1)，可以去掉最后一个1，对于2的次幂，本身只有一个1，所以上题可以((n & (n-1)) == 0这么判断。

/**
 191. 位1的个数
 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。



 提示：

 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。


 示例 1：

 输入：00000000000000000000000000001011
 输出：3
 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
 示例 2：

 输入：00000000000000000000000010000000
 输出：1
 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
 示例 3：

 输入：11111111111111111111111111111101
 输出：31
 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。


 提示：

 输入必须是长度为 32 的 二进制串 。

 * @author zeroheart
 * @since 2022/4/4
 */
public class Question191 {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n!=0){
            res++;
            // 去除最后一位1（不一定是末尾的一位）
            n = n & (n - 1);
        }
        return res;

        // 这是几年前的写法。。。leecode的趋势也在变化
        //        int flag = 1;
        //        int count = 0;
        //        while (flag != 0){
        //            if((flag & n) != 0){
        //                count++;
        //            }
        //            flag = flag << 1;
        //        }
        //        return count;
    }

    public static void main(String[] args) {
    }


}