算法（四）——位运算与位图
文章目录
- 位运算、位图
- 位运算
- 基本位运算
- 异或运算
- 交换两个数
- 无比较返回最大值
- 缺失的数字
- 唯一出现奇数次的数
- 唯二出现奇数次的数
- 唯一出现次数少于m次的数
- 位运算进阶
- 判断一个整数是不是2的幂
- 判断一个整数是不是3的幂
- 大于等于n的最小的2的幂
- [left, right]内所有数字&的结果
- 反转一个二进制状态
- 返回一个数二进制中有几个1
- 位图
- 概念及实现
- 题目练习
位运算、位图
位运算
基本位运算
列举几个有关位运算的常识（常用或是简单易混）：
-
>>：算术右移，右移后左端补符号位；>>>逻辑右移，右移后左端补0 -
位运算取相反数：
~num + 1。int、long类型的最小值的相反数还是自己，这是由它们的取值范围决定的 -
打印一个二进制数（
int为例）：public static void printBinary1(int num) { for(int i = 31; i >= 0; i--) { System.out.print((num & (1 << i)) == 0 ? 0 : 1); } }具体式子有很多，关键是理解，再比如：
public static void printBinary2(int num) { for(int i = 31; i >= 0; i--) { System.out.print((num >> i) & 1); } }
异或运算
异或运算的性质：
- 异或运算就是无进位相加
- 异或运算满足交换律、结合律（不论异或顺序是什么，同一批数字的异或和不变）
0 ^ n = n、n ^ n = 0- 整体异或和为
x，其中一部分的异或和是y，则剩下部分的异或和为x ^ y
交换两个数
不使用第三个变量，交换两个数：
int a = 10;
int b = 5;
a = a ^ b;//a: a ^ b b: b
b = a ^ b;//b = a ^ b ^ b = a a = a ^ b
a = a ^ b;//a = a ^ b ^ a = b
System.out.println(a);
System.out.println(b);
- 如表格：
| 语句 | a | b |
|---|---|---|
a = a ^ b | a ^ b | b |
b = a ^ b | a ^ b | a（a ^ b ^ b） |
a = a ^ b | b（a ^ b ^ a） | a |
无比较返回最大值
这是一个看起来比较绕但是很高效的实现：
/**
* 将负数返回1，非负返回0 => 负数返回0，非负返回1
* @param n
* @return
*/
public static int flip(int n) {
//翻转，0变1，1变0
return n ^ 1;
}
public static int sign(int n) {
//拿到翻转后的符号位，使得1表示非负，0表示负数
return flip(n >>> 31);
}
/**
* 有溢出风险
* c 可能溢出
* @param a
* @param b
* @return
*/
public static int getMax1(int a, int b) {
int c = a - b;
int returnA = sign(c);
int returnB = flip(returnA);
//returnA和returnB一定是相反的
return a * returnA + b * returnB;
}
/**
* 无溢出风险
* @param a
* @param b
* @return
*/
public static int getMax2(int a, int b) {
int c = a - b;//此时c可能溢出，可能不溢出
//a、b、c的符号
int sa = sign(a);
int sb = sign(b);
int sc = sign(c);
int diffAB = sa ^ sb;//判断a、b的符号是否一样
int sameAB = flip(diffAB);
int returnA = sa * diffAB + sc * sameAB;
int returnB = flip(returnA);
return a * returnA + b * returnB;
}
-
解释有溢出风险的实现：
c变量存储a - b的差值，returnA拿到c的符号位，c为非负数返回1，否则返回0,；returnB是returnA翻转。a * returnA + b * returnB：如果a大，则c变量存储的是正数，returnA经sign(c)拿到的就是1，returnB拿到的是0，代入式子可知返回值就是a；b大的情况同理可知。 -
然而
int c = a - b存在溢出风险，使得c的值是一个不准确的值，例如：当a是一个较大的正数，b是一个较大的负数的情况，就很容易发生溢出。解释无溢出风险的实现：仍然先计算
a - b，结果存在c中，此时c是否因溢出而不准确无法确定；拿到a、b、c三个数的符号；diffAB = sa ^ sb，即当a和b符号相同，diffAB存储0，相反存储1，sameAB是diffAB的翻转returnA = sa * diffAB + sc * sameAB：returnA == 1当且仅当sa == 1 && diffAB == 1或sc == 1 && sameAB == 1。sa == 1 && diffAB == 1：a和b符号不同，a为正数，b为负数，a > b最终返回a；sc == 1 && sameAB == 1：a和b符号相同（不会发生溢出），c为正数，a > b最终返回a。最终
return a * returnA + b * returnB;符合预期。
缺失的数字
原题链接：面试题 17.04. 消失的数字 - 力扣（LeetCode）
这道题目用到 整体异或和为x，其中一部分的异或和是y，则剩下部分的异或和为x ^ y 这个性质（结论），0~n就是整体，所给数组就是部分，对两个集合分别求得异或和，然后再异或得到的结果就是缺失的数字。
之所以这么容易，也是因为只缺失了一个数字。
【代码实现】
class Solution {
public int missingNumber(int[] nums) {
int xorSum = 0;
int numSum = 0;
for(int i = 0; i < nums.length; i++) {
xorSum ^= i;
numSum ^= nums[i];
}
xorSum ^= nums.length;
return xorSum ^ numSum;
}
}
唯一出现奇数次的数
给定一个数组，其中只有一个数只出现了奇数次，求这个数。
很简单，只需要将数组的所有元素异或得到的异或和就是所求数字。因为出现偶数次的数都两两相消成0了，因此最终剩下的就是唯一出现奇数次的数。
测试链接：136. 只出现一次的数字 - 力扣（LeetCode）
class Solution {
public int singleNumber(int[] nums) {
int xorSum = 0;
for(int num : nums) {
xorSum ^= num;
}
return xorSum;
}
}
- 这道题目只是其中一种情况，出现1次就是奇数次，2次就是偶数次。
唯二出现奇数次的数
提取二进制状态中最右侧的1：
这是 Brian Kernighan算法 的关键部分，具体做法其实很简单：
假设要提取
n的二进制状态中最右侧的1，只需要n & (~n + 1)，等价于n & (-n)。简单用8位验证一下：
表达式 结果 n0010 1010 ~n1101 0101 ~n + 11101 0110 n & (~n + 1)0000 0010
思路：假设唯二出现奇数次的数为a和b
先求所有数的异或和，存放到假设eor1中，则eor1 = a ^ b（出现偶数次的都两两相消了）；既然a和b是不相等的数，那么a ^ b的表示的二进制状态中一定存在 1，为 1 的位上对应a和b的状态一定是相反的（一个是1一个是0），利用上面提到的算法可以得到最右侧的1的状态，然后根据这一位上的状态可以将原数组的数分为两部分，一部分数的这一位是1；另一部分数的这一位是0，a和b一定不在同一个部分， 然后再次遍历原数组，只将这一位为1（当然为0也可以）的数字异或起来得到一个异或和放到假设eor2中，则eor2一定是a、b的其中一个（因为偶数次的数字还是会相消），然后另一个为eor1 ^ eor2（eor1 = a ^ b，假设eor2 = a，则b = eor1 ^ eor2；同理，如果eor2 = b，a = eor1 ^ eor2）
测试链接：260. 只出现一次的数字 III - 力扣（LeetCode）
class Solution {
public int[] singleNumber(int[] nums) {
int eor1 = 0;
int eor2 = 0;
for(int num : nums) {
eor1 ^= num;
}
//eor1 = a ^ b
int tmp = eor1 & (-eor1);
for(int num : nums) {
if((num & tmp) != 0) {
eor2 ^= num;
}
}
return new int[]{eor2, eor1 ^ eor2};
}
}
- 这道题目仍然是一种前面介绍的其中一种情况。
唯一出现次数少于m次的数
思路：维护一组记录，记录了遍历完所有数后，每一位上1出现的次数。如果某个记录代表的位上的1出现的次数 % m != 0，就代表这一位上1的次数曾经因为 出现次数少于m次的那个数 的出现而不再是m的整数倍，即要寻找的数的这一位上一定是1（如果是0的话就不会影响1出现次数的统计，也就能保证是m的整数倍了），我们只需要将每条这样的记录对应的位设置为1，得到的状态对应的数就是结果。
public int singleNumber(int[] nums, int m) {
int[] cnts = new int[32];
for(int num : nums) {
for(int i = 0; i < 32; i++) {
cnts[i] += num >> i & 1;
}
}
int ans = 0;
for(int i = 0; i < 32; i++) {
if(cnts[i] % m != 0) {
ans |= 1 << i;
}
}
return ans;
}
测试链接：137. 只出现一次的数字 II - 力扣（LeetCode）
class Solution {
public int singleNumber(int[] nums) {
int[] cnts = new int[32];
for(int num : nums) {
for(int i = 0; i < 32; i++) {
cnts[i] += num >> i & 1;
}
}
int ans = 0;
for(int i = 0; i < 32; i++) {
if(cnts[i] % 3 != 0) {
ans |= 1 << i;
}
}
return ans;
}
}
- 这道题目也是前面介绍的其中的一种情况，之前介绍的兼顾这道测试题目。
- 问题记录：对于
cnts[i] += num >> i & 1，不要误写成cnts[i] += num & (1 << i)，前者的num >> i & 1的结果集只有0和1，而后者num & (1 << i)的结果要么是 0，要么是2 ^ i，而我们只希望判断每个数每一个位是否是1而对相应的数组位置的值累加一次即可。
位运算进阶
判断一个整数是不是2的幂
一个是2的幂的整数有什么特点？它的二进制表示中只有一个位上的数字为1，因此，只需要利用 Brian Kernighan算法 拿到最左侧的1的状态，看这个状态的数值是否等于待检验整数即可。
测试链接：231. 2 的幂 - 力扣（LeetCode）
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & -n) == n;
}
}
- 当然2的幂一定是大于0的。
判断一个整数是不是3的幂
一个数是3的某次幂，则这个数一定只含有3这个质数因子。（质数因子是指一个数的因子中是质数的那些因子；质数是只能被1和它本身整除的大于1的整数；因子（因数）是指能够整除一个给定整数的数）
可以通过以下步骤来证明这个结论：
- 假设一个数字 n 是3的某次幂，即 n = 3 ^k，其中 k 是一个非负整数。
- 根据质数的定义，3是一个质数，它只有1和3两个正因数。
- 当我们计算 3 ^k 时，我们实际上是在将3这个质数乘以自己 k 次。因此， 3 ^k 的所有质数因子都是3。
- 由于 n=3 ^k，所以 n 的所有质数因子也都是3。这意味着 n 只含有3这个质数因子。
1162261467（3^19）是整形int范围内最大的3的幂，只含有3这个质数因子，那么如果一个数 n 也只含有3这个质数因子，则有1162261467 % n == 0；反之，1162261467 % n != 0
测试链接：326. 3 的幂 - 力扣（LeetCode）
class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
}
大于等于n的最小的2的幂
假设n为33，则返回64，因为32不满足大于等于的条件。这个算法的具体实现为：
public static final int nearTwoPower(int n) {
if (n <= 0) {
return 1;
}
n--;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return n + 1;
}
-
方法一开始的
if语句很好理解，即如果n的值小于等于0，假设-5，则大于等于-5的最小的2的幂一定是1。 -
n--的作用是确保当n的值就是2的幂时，能够返回n。如果没有这个语句，经过下面的逻辑后将会返回较大的2的幂，比如当n = 8时，如果没有提前n--，则最后返回的值将是16，这显然不符合预期。 -
n--和return语句之间的逻辑总结起来就是将n的二进制表示“扩展”到一个从最高位的 1 到最低位全为 1 的状态（刷为1）。表格演示
n == 37时的转换过程：操作 操作后n的状态（方便起见，仅展示最低的8位） n0010 0101（37）n--0010 0100`n = n >>> 1` `n = n >>> 2` `n = n >>> 4` `n = n >>> 8` `n = n >>> 16` n + 10100 0000（64）
这是一个实践性很强的算法，当我们查看Java 8的源码时，会发现这个算法的存在，具体操作如下图：
[left, right]内所有数字&的结果
测试链接：201. 数字范围按位与 - 力扣（LeetCode）
这个问题可以由下面的算法快速解决：
class Solution {
public int rangeBitwiseAnd(int left, int right) {
while(left < right) {
right -= right & (-right);
}
return right;
}
}
- 如果
left == right则意味着只有一个元素，此时不会进入循环直接返回right是符合预期的 - 如果
left < right则意味着：right - 1也一定在计算范围内，那么有什么用呢？- 有：所有的与项的某一位都是1，最终结果的这一位才会是1
right - 1即right的二进制表示的最右侧的1变为0，前面提到right - 1一定在计算范围内，则最终结果对应的right最右侧1的那个位上一定为0，因此right减去最右侧的1，然后继续判断left和right是否相等。- 每次循环，
right的二进制表示中最低位的 1 都会被变成 0。这相当于逐步“缩小”right的值，直到left和right相等。此时，right的值就是从left到right（包括left和right）的所有整数的按位与的结果。
反转一个二进制状态
反转一个二进制状态即二进制状态逆序，例如（四位举例）1101变为1011，大佬想出了一个高效的算法，这个算法不需要条件判断，十分高效：
public static int reverseBits(int n) {
n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
n = (n >>> 16) | (n << 16);
return n;
}
单看代码十分抽象，我们一点一点理解：
首先，大佬的整体思路是这样的：先一位一位的换，然后两位两位的换，接着四位四位的换，八位八位的换，最终十六位十六位的换，经过这样的多番轮换，最终就能逆序二进制。以8位二进制为例（与32位原理一致，只不过换完4v4那一轮即可）：
操作 此时的状态 无任何操作 1000 0101 1v1交换 0100 1010 2v2交换 0001 1010 4v4交换 1010 0001
- 结果显然正确，对于32位来说，拓展到16v16交换即可。
基本思路了解了，与代码有什么关系呢？
我们仍然假设一个8位的二进制为：
abcd efgh：先模拟1v1交换：
首先计算
(abcd efgh) & (1010 1010)，结果1对应的位信息会被留下来，0对应的位都变为0，得到a0c0 e0g0，然后将结果右移1位，得到0a0c 0e0g然后计算
(abcd efgh) & (0101 0101)，结果1对应的位信息会被留下来，0对应的位都变为0，得到0b0d 0f0h，然后将结果左移一位，得到b0d0 f0h0然后将上面两步的最终结果
|起来，即(0a0c 0e0g) | (b0d0 f0h0)，得到badc fehg，此时就完成了1v1的交换我们知道，二进制的4位代表十六进制的1位，
1010 1010转化为十六进制就是aa；0101 0101转化为十六进制就是55，我们是以8位二进制为例，因此对于32位的二进制完成1v1交换，需要的就是代码中的0xaaaaaaaa和0x55555555同理，接着实现2v2的交换：
首先计算
(badc fehg) & (1100 1100)，得到ba00 fe00，然后将结果右移2位，得到00ba 00fe然后计算
(badc fehg) & (0011 0011)，得到00dc 00hg，然后将结果左移2位，得到dc00 hg00将上面两步的结果
|起来，即(00ba 00fe) | (dc00 hg00)，得到dcba hgfe，此时就完成了2v2的交换
1100 1100转化为十六进制就是cc，0011 0011转化为十六进制就是33，此时再看代码就知道怎么回事了后续是同样的道理，自己下来可以举一个32位的例子验证一下。
测试链接：190. 颠倒二进制位 - 力扣（LeetCode）
public class Solution {
public static int reverseBits(int n) {
n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
n = (n >>> 16) | (n << 16);
return n;
}
}
返回一个数二进制中有几个1
题意很好理解，像1010 1000就返回3，但是大佬又想到了一个高效的方法，不需要循环：
public static int cntOnes(int n) {
n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);
return n;
}
这个算法的基本思想：
- 分组统计：将整数的二进制表示分成若干组，每组统计 1 的数量。
- 合并统计：将相邻的组合并，统计更大的范围内的 1 的数量。
- 逐步扩展：重复上述过程，直到统计完整个整数。
仍然以8位二进制举例：
0000 1101
初始状态
0000 1101，每一位算一个组，每组的数字就表示这一组中1的数量，显然此时分了8组，每一组1的数量就是每一组位上的数字。接着执行
n = (n & 0x55555555) + ((n >>> 1) & 0x55555555)：
n & 0x55555555：提取偶数位。
0000 1101 & 0101 0101 = 0000 0101(n >>> 1) & 0x55555555：提取奇数位并右移一位。
0000 1101 >>> 1 = 0000 01100000 0110 & 0101 0101 = 0000 0100- 将两者相加：
0000 0101 + 0000 0100 = 0000 1001这一步的结果：
0000 1001，每两位算一个组，每组的数字就表示这一组中1的数量，此时分了4组：00、00、10、01，每一组对应的1的个数：0、0、2、1接着执行
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333)：
n & 0x33333333：提取第0、1位和第4、5位。
0000 1001 & 0011 0011 = 0000 0001(n >>> 2) & 0x33333333：提取第2、3位和第6、7位，并右移两位。
0000 1001 >>> 2 = 0000 00100000 0010 & 0011 0011 = 0000 0010- 将两者相加：
0000 0001 + 0000 0010 = 0000 0011结果：
0000 0011，每四位分一组，显然分了2组：0000、0011，每一组对应的1的个数：0、3依次类推，拓展到8位为一组，如果是32位就逐步拓展到32位为一组，最后的值就是所有的1的数量。
测试链接：461. 汉明距离 - 力扣（LeetCode）
class Solution {
public int hammingDistance(int x, int y) {
int n = x ^ y;
n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);
return n;
}
}
- 这道题目没有直接说计算位为1的数量，而是提供了一个场景，利用异或运算的特性一转换再代入算法即可。
后面几个案例的代码的确很抽象，很强但似乎太得瑟了，其实不是的，这些代码是有现实意义的，因为：条件判断相比于赋值、位运算、算术运算是稍慢的，但是自己写算法时不需要追求不写条件判断，那样只会给自己找麻烦，至于大佬的实现欣赏并理解就好，下次直接当模板使用。
——左程云
位图
概念及实现
位图即用每一位来存放某种状态，适用于海量数据，整数，数据无重复的场景，通常是用来判断某个数据是否存在的。
腾讯曾经有一道面试题：给40亿个不重复的无符号整数，无序。快速判断一个无符号整数是否在这40亿个数中。
分析：如果遍历，时间复杂度为O(N)；如果先排序后二分，时间复杂度为O(N*logN + logN)。
先抛开时间不谈，我们不能忽略一点，就是存储问题，10亿个字节大约是1G，假设就用int类型存，10亿个整数大约是4G，40亿整数大概是16G，这是一个很大的数字，况且Java中int类型表示不下40亿个不重复的非负数，需要long类型。总之庞大的数据量导致我们连存储（以现在的内存）都是问题。
因此，引入了位图，位图其实就是哈希的应用，一个位代表一个数字，1表示存在，0表示不存在，存放和查找遵循某种映射关系。此时一个数字的信息从4字节（32位）或是8字节（64位）直接压缩至1位，同时查找时间复杂度为O(1)。
结合下图理解：
-
图中仅展示了3位，但是足以表示数字0~23，上面数组存在的数字都在位图里体现了
-
实际上位图本身通常是一个数组，可以是
byte类型的，也可以是int类型的等等。假设上图展示的就是一个
byte类型的数组，那么[1]存储的就是0~7数字的信息，后面的同理。此时假设将15插入位图，代码方面怎么处理？- 确定数组下标：15 / 8 = 1
- 确定在该下标的哪一位：15 % 8 = 7
- 设置为1即可
【代码实现】
有关位图，Java中有现成类BitSet，不过我们这里是要自己实现一个简单的位图类，熟悉位图常用方法和练习位运算。
public class BitSet {
public int[] set;
// n个数字 : 0~n-1
public BitSet(int n) {
set = new int[(n + 31) / 32];
}
/**
* 添加一个数字
* @param num
*/
public void add(int num) {
set[num / 32] |= 1 << (num % 32);
}
/**
* 移除一个数字
* @param num
*/
public void remove(int num) {
set[num / 32] &= ~(1 << (num % 32));
}
/**
* 反转一个数字，即原来存在变为不存在，不存在变为存在
* @param num
*/
public void reverse(int num) {
set[num / 32] ^= 1 << (num % 32);
}
/**
* 判断某个数字是否存在
* @param num
* @return
*/
public boolean contains(int num) {
return ((set[num / 32] >> (num % 32)) & 1) == 1;
}
}
- 具体实现因人而异，可以选择
byte[]数组，如果追求极致的严谨性可以在每个方法前加上一些判断，比如add方法判断加入的数字是否超出可表示的范围（但是如果我们提前知道了数据范围，准备好足够的空间即可），也可以加入一些属性，比如当前存在的有效数字的数量等等。 - 注意，
remove方法不能使用异或（set[num / 32] ^= 1 << (num % 32);），反例：当原来的位置上是0，那么异或后就变1，与移除方法逻辑不符 (n + 31) / 32是一个向上取整，当a和b都是非负数时，想要得到a除b的向上取整的写法：(a + b - 1) / b- 另外，使用位图进行排序：比较简单，依次遍历，为1就打印映射出的数字即可。
【对数器验证】
对于实现好的位图，可以选择对数器的方式验证，位图本质上还是哈希表，因此可以使用哈希表来作为对照，即生成一些随机数字，分别放入位图和哈希表中，进行一些添加删除操作，最后验证结果即可。
public static void main(String[] args) {
//测试范围0~4999
int n = 1000;
//测试次数
int testTimes = 10_000;
BitSet bitSet = new BitSet(n);
HashSet<Integer> hashSet = new HashSet<>();
Random random = new Random();
for(int i = 0; i < testTimes; i++) {
int op = random.nextInt(3);
int number = random.nextInt(1000);
if(op == 0) {
bitSet.add(number);
hashSet.add(number);
}else if(op == 1) {
bitSet.remove(number);
hashSet.remove(number);
}else {
bitSet.reverse(number);
if(hashSet.contains(number)) {
hashSet.remove(number);
}else {
hashSet.add(number);
}
}
}
System.out.println("验证阶段开始！");
for(int i = 0; i < n; i++) {
if(bitSet.contains(i) != hashSet.contains(i)) {
System.out.println("测试出错！");
}
}
System.out.println("验证阶段结束！");
}
-
思路：先规定数字范围和操作次数，然后进行规定次数的操作，具体操作和数字随机生成，位图和哈希表针对随机数字执行随机操作，最后验证容器中元素状态是否一致，如果出错则打印出错。
多次测试发现，代码无误。
题目练习
测试链接：2166. 设计位集 - 力扣（LeetCode）
一道实现位图的题目，理解了位图实现后难度不大，只是多了几个方法和要求，这里给出左程云大佬的实现：
class Bitset {
private int[] set;
private final int size;
private int zeros;
private int ones;
private boolean reverse;//标识是否翻转过，false就表示保持原含义，1存在，0不存在；true则相反，1为不存在，0存在
public Bitset(int n) {
set = new int[(n + 31) / 32];
size = n;
zeros = n;
ones = 0;
reverse = false;
}
// 把i这个数字加入到位图
public void fix(int i) {
int index = i / 32;
int bit = i % 32;
if (!reverse) {
// 位图所有位的状态，维持原始含义
// 0 : 不存在
// 1 : 存在
if ((set[index] & (1 << bit)) == 0) {
zeros--;
ones++;
set[index] |= (1 << bit);
}
} else {
// 位图所有位的状态，翻转了
// 0 : 存在
// 1 : 不存在
if ((set[index] & (1 << bit)) != 0) {
zeros--;
ones++;
set[index] ^= (1 << bit);
}
}
}
// 把i这个数字从位图中移除
public void unfix(int i) {
int index = i / 32;
int bit = i % 32;
if (!reverse) {
if ((set[index] & (1 << bit)) != 0) {
ones--;
zeros++;
set[index] ^= (1 << bit);
}
} else {
if ((set[index] & (1 << bit)) == 0) {
ones--;
zeros++;
set[index] |= (1 << bit);
}
}
}
public void flip() {
reverse = !reverse;
int tmp = zeros;
zeros = ones;
ones = tmp;
}
public boolean all() {
return ones == size;
}
public boolean one() {
return ones > 0;
}
public int count() {
return ones;
}
public String toString() {
StringBuilder builder = new StringBuilder();
for (int i = 0, k = 0, number, status; i < size; k++) {
number = set[k];
for (int j = 0; j < 32 && i < size; j++, i++) {
status = (number >> j) & 1;
status ^= reverse ? 1 : 0;
builder.append(status);
}
}
return builder.toString();
}
}
- 这种实现的效率是很高的（至少比我写的高），通过维护一个布尔变量
reverse来避免翻转方法的遍历。
完