191. Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

求一个32位数在二进制表示下的1的个数。

package _191;

public class Solution {
    //借用下树状数组=^=
    int LowBit(int x) {
        return x & (-x);
    }
    public int hammingWeight(int n) {
        int result = 0;
        while (n != 0) {
            result++;
            n = n - LowBit(n);
        }
        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        for (int i = 0; i <=16 ; i++) {
            System.out.println(i + " " + solution.hammingWeight(i));
        }
    }
}

回一下树状数组的LowBit：

我们另：

C[1] = A[1];

C[2] = A[2] + A[1] ;

C[3] = A[3];

C[4] = A[4] + A[3] + A[2] + A[1] ;

C[5] = A[5];

C[6] = A[6] + A[5] ;

C[7] = A[7];

C[8] = A[8] + A[7] + A[6] + A[5] + A[4] + A[3] + A[2] + A[1] ;

S[i]=A[1]+A[2]+...+A[i]

S[1] = C[1]；1的二进制表示有1个1

S[2] = C[2]；2的二进制表示有1个1

S[3] = C[3] + C[2]；3的二进制表示有1个2

S[4] = C[4]；4的二进制表示有1个1

S[5] = C[5] + C[4]；5的二进制表示有1个2

S[6] = C[6] + C[4]；6的二进制表示有1个2

S[7] = C[7] + C[6] + C[4]；7的二进制表示有1个3

S[8] = C[8]；8的二进制表示有1个1

i二进制位中1的个数等于上述每个表达式中S[i]中由多少个C[]组成，好神奇。

而S[i] = C[i] + C[i - LowBit(i)]+....一直到i - LowBit(i)为0

详细解释见：树状数组学习笔记

231. Power of Two

Given an integer, write a function to determine if it is a power of two.

判断一个数是不是2的幂。

2的幂：其二进制位只有一个1，且在最左面，其右边所有的数都是0.如1-->1;2-->10;4-->100;8-->1000

package _231;

public class Solution {
    private int LowBit(int x) {
        return  x & (-x);
    }
    public boolean isPowerOfTwo(int n) {
        boolean flag = false;
        if (n <= 0) {
            return false;
        }
        if (n - LowBit(n) == 0) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isPowerOfTwo(-16));
    }
}

342. Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

package _342;

public class Solution {
    private int LowBit(int x) {
        return  x & (-x);
    }
    public boolean isPowerOfFour(int num) {
        if (num <= 0) {
            return false;
        }
        if (num - LowBit(num) != 0) {
            return false;
        }
        num--;
        int result = 0;
        while (num != 0) {
            result++;
            num -= LowBit(num);
        }
        if (result % 2 == 0) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isPowerOfFour(32));
    }
}

其实还有个简单的方法。

n & (n - 1) --> 删除n最末尾的 1。