常用位运算技巧

位运算符：

  1. & 与：要求所有表达式的判断结果都是 1 才为 1；
  2. | 或：要求所有表达式的判断结果都是 0 才为 0；
  3. ^ 异或：如果a、b两个值不相同，则异或结果为 1。如果a、b两个值相同，异或结果为 0；
  4. ! 非：取反。

1. n & (n - 1) 的妙用

描述：将 n 的二进制表示中的最低位为 1 的改为 0 。

例子： n = (1010)2、(n - 1) = (1001)2，那么 n & ( n - 1) = (1000)2

2. 获取二进制的最高位和最低位

  1. 获取高位 n & (1 << 31)
  2. 获取低位 n &1

例题

题目要求

664 · 数 1：https://www.lintcode.com/problem/664/

描述：给出一个 非负 整数 num，对所有满足 0 ≤ i ≤ num 条件的数字 i 均需要计算其二进制表示中数字 1 的个数并以数组的形式返回。

样例：

样例1：

1
2
3
4
5
6
7
8
9
10
11
输入： 5
输出： [0,1,1,2,1,2]
解释：
0~5的二进制表示分别是：
000
001
010
011
100
101
每个数字中1的个数为： 0,1,1,2,1,2

样例2：

1
2
输入： 3
输出： [0,1,1,2]

挑战

  1. 时间复杂度为 O(n * sizeof(integer)) 的解法很容易想到, 尝试挑战线性的时间复杂度 O(n) (只遍历一遍)。
  2. 空间复杂度应为 O(n)。
  3. 你能完成这项挑战吗? 不借助任何内嵌的函数, 比如 C++ 中的 __builtin_popcount 亦或是任何其他语言中的方法。

题目分析

  1. 本题是动态规划和位运算的结合；
  2. 例如 n = (10)10 = (1010)2、，那么 n 中有两个 1；
  3. 运用位运算去掉 n 的最后一个 1；
  4. 即 n & ( n - 1) = (1010)2 & (1001)2 = (8)10 = (1000)2；
  5. 用 dp[i] 表示 i 中有几个 1，那么由上可得 dp[10] = dp[8] + 1；
  6. 即状态转移方程为 dp[i] = dp[i & (i - 1)] + 1。

代码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution 
{
    /**
     * @param num: a non negative integer number
     * @return: an array represent the number of 1's in their binary
     */
    public int[] countBits(int num) 
    {
        // write your code here        
        int[] dp = new int[num + 1];
        if (num == 0) return dp;
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) 
        {
            dp[i] = dp[i & (i - 1)] + 1;          
        }
        return dp;
    }
}


📌最后：希望本文能够给您提供帮助，文章中有不懂或不正确的地方，请在下方评论区💬留言！