龙岩市住房与城乡建设部网站,wordpress本地更新,网络服务协议模板,网站注册免费适用场景#xff1a;整数#xff0c;无重复#xff1b;Bitset 基础Bitset#xff0c;也就是位图#xff0c;由于可以用非常紧凑的格式来表示给定范围的连续数据而经常出现在各种算法设计中。上面的图来自c库中bitset的一张图。基本原理是#xff0c;用1位来表示一个数据是…适用场景整数无重复Bitset 基础Bitset也就是位图由于可以用非常紧凑的格式来表示给定范围的连续数据而经常出现在各种算法设计中。上面的图来自c库中bitset的一张图。基本原理是用1位来表示一个数据是否出现过0为没有出现过1表示出现过。使用用的时候既可根据某一个是否为0表示此数是否出现过。一个1G的空间有 81024102410248.5810^9bit也就是可以表示85亿个不同的数。常见的应用是那些需要对海量数据进行一些统计工作的时候比如日志分析等。面试题中也常出现比如统计40亿个数据中没有出现的数据将40亿个不同数据进行排序等。又如现在有1千万个随机数随机数的范围在1到1亿之间。现在要求写出一种算法将1到1亿之间没有在随机数中的数求出来(百度)。programming pearls上也有一个关于使用bitset来查找电话号码的题目。Bitmap的常见扩展是用2位或者更多为来表示此数字的更多信息比如出现了多少次等。Java中Bitset的实现Bitset这种结构虽然简单实现的时候也有一些细节需要主要。其中的关键是一些位操作比如如何将指定位进行反转、设置、查询指定位的状态(0或者1)等。 本文分析一下java中bitset的实现抛砖引玉希望给那些需要自己设计位图结构的需要的程序员有所启发。Bitmap的基本操作有初始化一个bitset指定大小。清空bitset。反转某一指定位。设置某一指定位。获取某一位的状态。当前bitset的bit总位数。使用场景常见的应用是那些需要对海量数据进行一些统计工作的时候比如日志分析、用户数统计等等如统计40亿个数据中没有出现的数据将40亿个不同数据进行排序等。现在有1千万个随机数随机数的范围在1到1亿之间。现在要求写出一种算法将1到1亿之间没有在随机数中的数求出来代码示例package util; import java.util.Arrays;import java.util.BitSet; public class BitSetDemo { /** * 求一个字符串包含的char * */public static void containChars(String str) {BitSet used new BitSet();for (int i 0; i str.length(); i)used.set(str.charAt(i)); // set bit for char StringBuilder sb new StringBuilder();sb.append([);int size used.size();System.out.println(size);for (int i 0; i size; i) {if (used.get(i)) {sb.append((char) i);}}sb.append(]);System.out.println(sb.toString());} /** * 求素数 有无限个。一个大于1的自然数如果除了1和它本身外不能被其他自然数整除(除0以外)的数称之为素数(质数) 否则称为合数 */public static void computePrime() {BitSet sieve new BitSet(1024);int size sieve.size();for (int i 2; i size; i)sieve.set(i);int finalBit (int) Math.sqrt(sieve.size()); for (int i 2; i finalBit; i)if (sieve.get(i))for (int j 2 * i; j size; j i)sieve.clear(j); int counter 0;for (int i 1; i size; i) {if (sieve.get(i)) {System.out.printf(%5d
