n & (n-1)

• 算是一个小trick！
• n&(n-1)可消除n中最右边(低位)的一个1

 0101 1000 n
 0101 0111 n - 1    
 0101 0000 n & (n-1)

191. Number of 1 Bits

统计一个整数用二进制表示时1的个数

// Java
public int hammingWeight(int n) {
    int cnt = 0;
    while (n != 0) {
        cnt++;
        n &= (n - 1);
    }
    return cnt;
}

231. Power of Two

判断一个数是不是2的n次幂

0000 0001 2^0
0000 0010 2^1
0000 0100 2^2
0000 1000 2^3

// Java
class Solution {
    public boolean isPowerOfTwo(int n) {
        return (n > 0) && (((n - 1) & n) == 0);
    }
}

326. Power of Three

• 也有一行代码更数学上tricky的方法：return n > 0 && 1162261467 % n == 0;

// Java1 - Math
public class Solution {
    public boolean isPowerOfThree(int n) {
        return (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }
}

// Java2 - Forloop
class Solution {
    public boolean isPowerOfThree(int n) {
        while (n > 0 && (n%3 == 0)) {
            n /= 3;
        }
        return n == 1;
    }
}

342. Power of Four

// Java1 for loop
class Solution:
    def isPowerOfFour(self, n):
        if n < 1:
            return False
        while n % 4 == 0:
            n = n / 4
        return n == 1

// Java2 Math
// 0000 0001 1
// 0000 0100 4
// 0001 0000 16
// 0100 0000 64
class Solution {
    public boolean isPowerOfFour(int n) {
        //一个数学的方法：(4^n - 1) is multiple of 3
        return (n > 0) && (n&(n-1)) == 0 && (n-1) % 3 == 0;
    }
}

461. Hamming Distance

两个整数的汉明距离是指其二进制不相等的位的个数

class Solution(object):
    def hammingDistance(self, x, y):
        n = x ^ y # => Count bits of a number
        cnt = 0
        while n:
            n &= (n-1)
            cnt += 1
        return cnt

    def hammingDistance1(self, x, y):
        n = x ^ y
        cnt = 0
        while n:
            cnt += n & 1
            n >>= 1
        return cnt

477. Total Hamming Distance

两个整数的汉明距离是指其二进制不相等的位的个数, 计算给定的整数数组两两之间的汉明距离之和。

• 解法1. n^2 paris (TLE)

• 解法2. 拆解integer

  # Time : O(32 * n), Space : O(1)
  class Solution(object):
    def totalHammingDistance(self, nums):
        n = len(nums)
        if n <= 1: return 0
  
        res = 0
        mask = 1
        for _ in xrange(32):
            cnt1 = 0  
            for num in nums:
                if num & mask:
                    cnt1 += 1
            mask <<= 1
            res += (n - cnt1) * cnt1
        return res
  

201. Bitwise AND of Numbers Range

# [26, 30]
11010
11011
11100
11101
11110

仔细观察这个过程我们可以得出^_^，最后的结果是该范围内所有数的左边的共同部分，即公共左边首部(left header)

class Solution(object):
    def rangeBitwiseAnd(self, m, n):
        while m < n:
            n &= n-1
        return n