当前访客身份：游客 [
当前位置：
发布于 日 22时,
来由：（腾讯面试题）给40亿个不重复的unsignedint的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？可以用一个数字的二进制位来表示多个数字。例如&&这样的二进制可以表示&1,6,7,8&四个数字。一个&int类型有32位，可以表示32个数字。（理论上可以，但是实际上要留一个做符号位，也就是说能存储31位数字。如果是1000&……000这样的二进制，会溢出）///////////////////////////////////////////////////////////之前我的算法有不少问题，多谢楼里的朋友指出，给了我新的思路。现在我修改了代码的实现。新的代码我使用了位操作，提升了效率，也使代码更清晰。我想，我还是保留这个漏洞百出的代码。引以为戒。
代码片段(3)
1.&[代码]第一次修改后的实现（依赖下面的，BitUtil）&&&&
package com.primer.
import java.util.R
* 问题出处：* 给40亿个不重复的unsignedint的整数，没排过序的，
* 然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
* @author sd
public class BitMapTest {
* 解题思路，用bitmap（位图）的方式节约空间
* int共有32位(留一个符号位)。一个int可以表示 0～31之间的数字。可以申请一个数组，a[0]可以表示0～31
* a[1] 表示 32～63 以此类推。
* 将一连串的数字 初始化到 bitmap中
* @param numArr 给出的数字数组
* @param bitMap 待初始化的数组
public static void initBitMap(int[] numArr , int[] bitMap){
for(int i = 0 ; i & numArr. i++){
int index = getIndex(numArr[i]);
int destnum = getMod(numArr[i]);
adjustBitMap(destnum, bitMap, index);
* 算法主要做的工作
* 将 0～31之间的数字存入到bitmap中。 最高位符号位置位为0（正数）
一个a[0]数字 用32位可以表示成 1010……要调整这个数字
* @param pos 要存入的数字的存储位置（在 0 ～31之间）
* @param bitMap
* @param index 数组索引
public static void adjustBitMap(int pos , int[] bitMap , int index){
if(pos &31 && pos & -1){
int num = BitUtil.setBitByPos(bitMap[index], pos, 1);//将这个数字对应的位置位为1
bitMap[index] =
* 查找着数字是否在bitmap中（查找这个数字对应的位为0还是为1）
* @param destNum 要查找的数字
* @param bitMap 已经初始化的bitmap
public static int findNum(int destNum , int[] bitMap){
* 查找 destNum在bitMap中存储的位置。如果该位为1 ，则这个数字已经存在，否则不存在
int index = getIndex(destNum);
if(index & bitMap.length){
int pos = getMod(destNum);
int numpre = bitMap[index];
int bitset = BitUtil.getBitSet(numpre, pos);
public int isset(int a,int bit){
if((a&1)==0)
* 获取 这个数字存储在bitmap中的索引位置（0～30 存在 a1中）
* @param srcNum
public static int getIndex(int srcNum ){
return srcNum / 32;
public static int getMod(int srcNum){
return srcNum % 32;
* 初始化 要存入bitmap中的数字
* @param numArr
public static void initNumArr(int[] numArr){
int limitNum = numArr.
Random ran = new Random();
for(int i = 0 ; i & limitN i++){
numArr[i] = ran.nextInt(limitNum);
public static void main(String[] args){
int searchNum = 56;
int searchNum = 66;
int[] numArr = {19, 64, 45, 56, 0, 54, 28, 2, 23, 34, 40, 18, 54, 50, 49, 29, 20, 31, 47, 30, 24, 17, 50, 57, 33, 55, 21, 22, 27, 45, 3, 19, 17, 49, 24, 5, 15, 24, 27, 35, 6, 53, 9, 61, 4, 6, 12, 23, 52, 48, 39, 39, 21, 1, 11};
int map_length = numArr.length % 32==0?numArr.length/32 : numArr.length/32+1;
int[] bitMap = new int[map_length+1];
initBitMap(numArr, bitMap);
System.out.println(Arrays.toString(bitMap));
int find = findNum(searchNum, bitMap);
System.out.println(find);
2.&[代码]位操作工具，将某一位置位为0（或者1），获取某一位是为0还是为1&&&&
package com.primer.
public class BitUtil {
* 将一个数字的某一位置位为 0 或者置位为1
* @param numpre
* @param pos 0~31
* @param setnum 0或者1
* @return 置位后的数字
public static int setBitByPos(int numpre , int pos , int setnum){
if(setnum == 1 ){
numpre |= (1&&pos);
numpre &= ~(1 && pos);
* 获取某一位的二进制
* @param num
* @param pos 0~31
public static int getBitSet(int num,int pos){
if((num&1)==0){
public static void main(String[] args){
int numpre = 0;
int pos = 31;
int setnum = 1;
int num = setBitByPos(numpre, pos, setnum);
System.out.println(Integer.toBinaryString(num));
int num = getBitSet(numpre , pos);
System.out.println(num);
3.&[代码]bitmap
////这个程序我写的很糟糕，作为失败的典型，还是很成功的，XDDDD&&&&
package com.primer.
import java.util.A
import java.util.R
* 给40亿个不重复的unsignedint的整数，没排过序的，
* 然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
* @author sd
public class BitMapDemo {
* 解题思路，用bitmap（位图）的方式节约空间
* int共有32位(留一个符号位)。一个int可以表示 0～30之间的数字。可以申请一个数组，a[0]可以表示0～30
* a[1] 表示 31～61 以此类推。
* TODO tip:最高位留0
* 这样只能保留到0～30
* 每一个数字智能 存储31个数字
* test 100*32
* 申请一个数组
int[] bitmap = new int[100];
* 将一连串的数字 初始化到 bitmap中
* @param numArr 给出的数字数组
* @param bitMap 待初始化的数组
public static void initBitMap(int[] numArr , int[] bitMap){
for(int i = 0 ; i & numArr. i++){
int index = getIndex(numArr[i]);
int destnum = getMod(numArr[i]);
System.out.println("src "+numArr[i]+"getindex:"+index+"get destnum"+destnum);
adjustBitMap(destnum, bitMap, index);
* 算法主要做的工作
* 将 0～30之间的数字存入到bitmap中。 最高位符号位置位为0（正数）
一个a[0]数字 用32位可以表示成 1010……要调整这个数字
destnum 0 第2位，1 第3位---30 第 32 位
* @param destnum 要存入的数字（在 0 ～31之间）
* @param bitMap
* @param index 数组索引
public static void adjustBitMap(int destnum , int[] bitMap , int index){
if(destnum &31 && destnum & -1){
int numpre = bitMap[index];
String binary_str = Integer.toBinaryString(numpre);
binary_str = adjustBinaryStr(binary_str);
char[] cArr = binary_str.toCharArray();
System.out.println(cArr.length);
cArr[destnum+1] = '1';
System.out.println("get binary str result "+String.valueOf(cArr));
int num_result = Integer.valueOf(String.valueOf(cArr), 2);
bitMap[index] = num_
* 将已知的二进制串改写成有32位的字符串
* @param srcBinaryStr
public static String adjustBinaryStr(String srcBinaryStr){
int str_length = srcBinaryStr.length();
if(str_length & 32){
for(int i = 0 ; i & 32-str_ i++){
srcBinaryStr = "0"+srcBinaryS
return srcBinaryS
* 查找着数字是否在bitmap中
* @param destNum 要查找的数字
* @param bitMap 已经初始化的bitmap
public static boolean findNum(int destNum , int[] bitMap){
int index = getIndex(destNum);
int mod = getMod(destNum);
int numpre = bitMap[index];
String binary_str = Integer.toBinaryString(numpre);
binary_str = adjustBinaryStr(binary_str);
char[] cArr = binary_str.toCharArray();
System.out.println(cArr.length);
boolean flag =
if(cArr[mod+1] == '1'){
System.out.println("get binary str result "+String.valueOf(cArr));
int num_result = Integer.valueOf(String.valueOf(cArr), 2);
bitMap[index] = num_
* 获取 这个数字存储在bitmap中的索引位置（0～30 存在 a1中）
* @param srcNum
public static int getIndex(int srcNum ){
return srcNum / 31;
public static int getMod(int srcNum){
return srcNum % 31;
* 初始化 要存入bitmap中的数字
* @param numArr
public static void initNumArr(int[] numArr){
int limitNum = numArr.
Random ran = new Random();
for(int i = 0 ; i & limitN i++){
numArr[i] = ran.nextInt(limitNum);
public static void main(String[] args){
String srcBinaryStr = "100";
srcBinaryStr = adjustBinaryStr(srcBinaryStr);
System.out.println(srcBinaryStr);
System.out.println("0000011".length());
int[] bitMap = new int[2];
int destnum = 2;
int index = 0;
adjustBitMap(0, bitMap, 1);
adjustBitMap(1, bitMap, 1);
adjustBitMap(2, bitMap, 1);
adjustBitMap(3, bitMap, 1);
adjustBitMap(29, bitMap, 1);
adjustBitMap(30, bitMap, 1);
System.out.println(Arrays.toString(bitMap));
System.out.println(Integer.toBinaryString(bitMap[1]));
int srcNum = 63;
int index = getIndex(srcNum);
int mod = getMod(srcNum);
System.out.println("index:"+index+"mod:"+mod);
int searchNum = 56;
int searchNum = 66;
int[] numArr = {19, 64, 45, 56, 0, 54, 28, 2, 23, 34, 40, 18, 54, 50, 49, 29, 20, 31, 47, 30, 24, 17, 50, 57, 33, 55, 21, 22, 27, 45, 3, 19, 17, 49, 24, 5, 15, 24, 27, 35, 6, 53, 9, 61, 4, 6, 12, 23, 52, 48, 39, 39, 21, 1, 11};
int[] numArr = new int[55];
initNumArr(numArr);
System.out.println(Arrays.toString(numArr));
Arrays.sort(numArr);
System.out.println(Arrays.toString(numArr));
int map_length = numArr.length % 32==0?numArr.length/32 : numArr.length/32+1;
int[] bitMap = new int[map_length+1];
initBitMap(numArr, bitMap);
System.out.println(Arrays.toString(bitMap));
boolean find = findNum(searchNum, bitMap);
System.out.println(find);
开源中国-程序员在线工具：
相关的代码(139)
41回/5934阅
76回/6300阅
11回/2413阅
哎 看不懂。。。
2楼：kongnanlive 发表于
unsignedint：
C语言中在32位机，int、unsigned int 一般占用4个字节，short int一般占用2个字节，double一般占用8个字节。
int 是整型 有16位 能表示从 &—3之间的数字 Unsigned int &16位 是无符号整型 &0到 65535 short int &跟int 没什么差别 都是16位 表示数字的范围也一样 double 则是实型变量 有64位 具体请参阅float型数据
3楼：刘超71 发表于
这句话没看懂。。例如&&这样的二进制可以表示&1,6,7,8&四个数字？？ java有专门用于处理位的BitSet
4楼：alex-J 发表于
这个符号位，为什么不能用，做BitMap，这个没影响的，最多是负数，把他带进来，麻烦了
按你的思路实现了个&
5楼：moyiguke 发表于
引用来自“刘超71”的评论这句话没看懂。。例如&&这样的二进制可以表示&1,6,7,8&四个数字？？ java有专门用于处理位的BitSet我之前没有用过bitset这个东西。恩，要去看看资料了。 这里我的注释确实没有写好…… 我对bitmap的理解是这样的。一个整数有32位。00 00 。 如果数组有 1，6，7，8这些值。那么 这个整数 可以写成 00 00
。对应的十进制为。这样就可以用一个32位的整数来表示多个数字。
6楼：moyiguke 发表于
引用来自“alex-J”的评论这个符号位，为什么不能用，做BitMap，这个没影响的，最多是负数，把他带进来，麻烦了
按你的思路实现了个&
我保留这个符号位主要是因为在实现的时候，发现 第一位置位为1的时候 00 00
.这个数值超出了int的表示范围。所以我把第一位留空。
开源从代码分享开始
moyiguke的其他代码扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
c语言，第03章_数据类型
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口C语言里 -1用%u形式输出为什么是65535啊？为什么不是1呢？_百度知道
C语言里 -1用%u形式输出为什么是65535啊？为什么不是1呢？
C语言里 -1用%u形式输出为什么是65535啊？为什么不是1呢？我很菜 麻烦讲得基础点~~~
那1的存储形式是 11 1111 可是用%u输出还是1啊？
提问者采纳
计算机中的数 对应的二进制第一位在有符号时，1为负，0为正所以-1的首位是1再者负数的存储是不用原码的，而是补码所以-1的%u就是65535了（11 1111）
其他类似问题
为您推荐：
其他4条回答
无符号不是说把负号去掉，而是把最高位的1不看作负号。-1存储的形式为11 1111(补码)，最高位1不看作负号，计算得65535。1的存储是00 0001正数的补码和原码是一样的，不变
兄弟，你该补补基础了，x86里存储形式是补码，有符号数1的补码如果当作无符号数是1，-1的补码如果当作无符号数是65535
无符号数-1 -- 不是1，用它的补码
1的存储形式是00 0001
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁C语言，这一段怎么理解 如果该数被声明为无符号整型，则其最高位置为1后，该数变成了6553，而如果_百度知道
C语言，这一段怎么理解 如果该数被声明为无符号整型，则其最高位置为1后，该数变成了6553，而如果
C语言，这一段怎么理解如果该数被声明为无符号整型，则其最高位置为1后，该数变成了6553，而如果该数被声明为无有符号整型，则将其最高位置为1后， 该数将被解释为-1.
提问者采纳
首先你要搞清楚补码这个概念，计算机中所有的数值都是以补码形式储存在内存里面的第二个概念是，有符号数的二进制位中的最高位为符号位，符号位置1，则为负数，否则为正数你看看能不能理解，有问题请追问
提问者评价
其他类似问题
为您推荐：
无符号整型的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁