java 位运算 + leetcode 22.8.3 前n个数字二进制中1的个数

java 位运算

java位运算符是对操作数的二进制位进行运算，操作数和计算结果都是整型，位运算符如下：

&:

两个二进制位中只要有一个为0那么结果就为0，否则为1。

|:

两个二进制位中只要有一个为1那么结果就为1，否则为0。

^:

任何两个相同的二进制位进行异或运算，结果都为0；不同的两个进行运算，结果为1。

~：

0 --> 1，1 --> 0

<<:

将符号左边的操作数左移指定的位数。

首先将左边的操作数转为二进制。

然后按照要求左移指定位数，左边最高位丢弃，右边补齐0。

3<<2
3的二进制：
00000000 00000000 00000000 00000011
左移2位，左边最高位丢弃，右边补齐0：
00000000 00000000 00000000 00001100
1
2
3
4
5

>>:

将符号左边的操作数右移指定的位数。

首先将左边的操作数转为二进制。

然后按照要求右移指定位数，最高位是0，左边补齐0；最高为是1，左边补齐1。

24>>2
24的二进制：
00000000 00000000 00000000 00011000
右移2位，最高位是0，左边补齐0；最高为是1，左边补齐1：
00000000 00000000 00000000 00000110
1
2
3
4
5

>>>:

将符号左边的操作数右移指定的位数。

首先将左边的操作数转为二进制。

然后按照要求右移指定位数，无论最高位是0还是1左边补齐0。

24>>>2
24的二进制：
00000000 00000000 00000000 00011000
右移2位，最高位无论是什么都补0：
00000000 00000000 00000000 00000110
1
2
3
4
5

代码分析

下面这段算法可以得出一个整型数字二进制形式中含有多少1。

这里用到了variable-precision SWAR 算法，应该是处理这个问题效率最高的通用算法了。

通过分析这个函数，我们来深入理解java的二进制位运算。

public static int countBits(int i) {
        i = (i&0x55555555)+((i>>>1)&0x55555555);
        i = (i&0x33333333)+((i>>>2)&0x33333333);
        i = (i&0x0f0f0f0f)+((i>>>4)&0x0f0f0f0f);
        i = (i&0x00ff00ff)+((i>>>8)&0x00ff00ff);
        i = (i&0x0000ffff)+((i>>>16)&0x0000ffff);
        return i;
    }
1
2
3
4
5
6
7
8

0x55555555，0x33333333，0x0f0f0f0f到底有啥用呢，其实在这里就是用来做掩码，来取奇偶位上的数，然后移位后进行二进制加法就可以记录更大范围内1的数量

我们可以把i的二进制位理解成：长度为32的数组，每个元素取值区间[0,1]，每个元素正好能代表这个位是不是1.

所以，问题就可以转化为，求这个数组的和。

根据分治法的思想，我们可以把相邻的两个数字相加，得到长度为16的数组，每个元素取值区间[0,2]。

并以此类推，最终求出总和。

前 n 个数字二进制中 1 的个数

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数 - 力扣（LeetCode）

解题在这里插入图片描述

public static int[] countBits(int n) {
    int[] arr = new int[n+1];
    for (int i = 0; i <= n; i++) {
        int b = i;
        b = (b&0x55555555)+((b>>>1)&0x55555555);
        b = (b&0x33333333)+((b>>>2)&0x33333333);
        b = (b&0x0f0f0f0f)+((b>>>4)&0x0f0f0f0f);
        b = (b&0x00ff00ff)+((b>>>8)&0x00ff00ff);
        b = (b&0x0000ffff)+((b>>>16)&0x0000ffff);
        arr[i]=b;
    }
   return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这里就用到了上面的位运算，该解法时间复杂度为O(N)，空间复杂度为O(1);