【送分】第六题位运算完

kevindavid

本帖最后由刘蕴学于 2012-5-20 12:37 编辑

导语：表要瞧不起基础，表要攀比工具，基础无所不能！真的是酱紫吗？
我不想知道你们的基础是多么烂，请原谅我用这个词，我只想知道，你敢不敢跟着我把这些题全做下去，直到完虐入学测试的考试，嗯，就这么简单。
觉得难的请认真看老毕视频第二天13-16四节视频。

第三个，仍然是集合
这个题稍微有点简单了，主要还是灵活运用，考思维的，第二题如果你掌握了，这题不难。
按照第二题的方式实现给定集合A{0,1....172,173}用一个int表示
这个题就是2个short(byte)的事情，我的说话方式以及描述都在误导你放弃最简单的方式。当然在实际开发中，如果这个连续的集合是可以预期的，尽量采用这种方式来传输或者保存，以减小空间占用。
举个例子吧，比如说服务端给客户端传递1个帖子，是不是得有楼层编号，这里你只需要告诉客户端有帖子有多少回复就行了，而不是每个回复的数据区都写一个int来传这个回复的编号。
也许你们觉得我这是无聊，是吃饱撑的，但我要说，工作中，你的想法会很多，如果一份代码，你每天都有想法，每天都在改，或者你是个完美主义者，那么你永远无法按时完成工作，你把大部分时间都浪费在你的所谓的更好的想法上了。
工作中的要点就是第一时间写出功能，不考虑优化（除非你确认你这个优化是有效的，你很熟练可以默写），等到项目完成之后，回过头来在去检验你的那些想法，没人会花钱雇佣一个不能按时完成工作的人。

由于原来的第二题可能有点不好理解，换个试试，上过初中的看不懂的自己撞墙去
第二个，集合
1.给定集合A{0,1,2.....30,31}
2.给定集合B{5,6....10,11}
3.求 A 和 B 的交集
4.求 A 和 B 的并集
5.求 B 相对于 A 的补集
6.求 A 对 B 差集
7.求给定集合 C{7,9} 是 A 和 B 哪个集合的子集，并实现任意集合子集的查询功能
8.以上所有集合必须使用一个int表示而非数组，所有代码均以按位运算符进行
9.使用查表法可以根据int表示的集合正确输出该集合所表示的数组。
10.必须详细写出解题思路，实现方法。去工作之后，你写的代码不是给你自己看的，是给别人看的，你不写设计思路，不写注释，你让人怎么看？
答案在25楼，24楼是位运算的笔记 22，23楼的解题思路你们也可以看下，而26楼是一个简单的用户权限实现，很基础的应用，真的权限机制比这个复杂太多。

第一个
用最简便的单循环输出如下，并详细写出原理以及解题思路，并说明其中问号处应该填什么？用字符串的木有小JJ，如果你真觉得等号后边的一排1没变化，那你可就错喽
本题13楼以及15楼的方式将不在有分，但是，还有另外一种方式，写的出来仍然有分。

11111111111111111111111111111110 ? 00000000000000000000000000000001 = 11111111111111111111111111111111
11111111111111111111111111111100 ? 00000000000000000000000000000011 = 11111111111111111111111111111111
11111111111111111111111111111000 ? 00000000000000000000000000000111 = 11111111111111111111111111111111
11111111111111111111111111110000 ? 00000000000000000000000000001111 = 11111111111111111111111111111111
11111111111111111111111111100000 ? 00000000000000000000000000011111 = 11111111111111111111111111111111
11111111111111111111111111000000 ? 00000000000000000000000000111111 = 11111111111111111111111111111111
11111111111111111111111110000000 ? 00000000000000000000000001111111 = 11111111111111111111111111111111
11111111111111111111111100000000 ? 00000000000000000000000011111111 = 11111111111111111111111111111111
11111111111111111111111000000000 ? 00000000000000000000000111111111 = 11111111111111111111111111111111
11111111111111111111110000000000 ? 00000000000000000000001111111111 = 11111111111111111111111111111111
11111111111111111111100000000000 ? 00000000000000000000011111111111 = 11111111111111111111111111111111
11111111111111111111000000000000 ? 00000000000000000000111111111111 = 11111111111111111111111111111111
11111111111111111110000000000000 ? 00000000000000000001111111111111 = 11111111111111111111111111111111
11111111111111111100000000000000 ? 00000000000000000011111111111111 = 11111111111111111111111111111111
11111111111111111000000000000000 ? 00000000000000000111111111111111 = 11111111111111111111111111111111
11111111111111110000000000000000 ? 00000000000000001111111111111111 = 11111111111111111111111111111111
11111111111111100000000000000000 ? 00000000000000011111111111111111 = 11111111111111111111111111111111
11111111111111000000000000000000 ? 00000000000000111111111111111111 = 11111111111111111111111111111111
11111111111110000000000000000000 ? 00000000000001111111111111111111 = 11111111111111111111111111111111
11111111111100000000000000000000 ? 00000000000011111111111111111111 = 11111111111111111111111111111111
11111111111000000000000000000000 ? 00000000000111111111111111111111 = 11111111111111111111111111111111
11111111110000000000000000000000 ? 00000000001111111111111111111111 = 11111111111111111111111111111111
11111111100000000000000000000000 ? 00000000011111111111111111111111 = 11111111111111111111111111111111
11111111000000000000000000000000 ? 00000000111111111111111111111111 = 11111111111111111111111111111111
11111110000000000000000000000000 ? 00000001111111111111111111111111 = 11111111111111111111111111111111
11111100000000000000000000000000 ? 00000011111111111111111111111111 = 11111111111111111111111111111111
11111000000000000000000000000000 ? 00000111111111111111111111111111 = 11111111111111111111111111111111
11110000000000000000000000000000 ? 00001111111111111111111111111111 = 11111111111111111111111111111111
11100000000000000000000000000000 ? 00011111111111111111111111111111 = 11111111111111111111111111111111
11000000000000000000000000000000 ? 00111111111111111111111111111111 = 11111111111111111111111111111111
10000000000000000000000000000000 ? 01111111111111111111111111111111 = 11111111111111111111111111111111

复制代码

这个题的考点不在于你到底对位运算有多了解，而是位移操作你是否熟练，以上图为例，这表示了3种唯一操作符，我是拿这个图来解释3种位移操作符的区别
第一列为左移，第二列为无符号右移，第三列为有符号位移，但单拿解题来说，前俩个操作求第三列也可以，恒值也可以，但主要是3列之间的关系。
如果你把第0行打印出来的话，第一行是第一列表示负数最大值，第一行第二列0表示正数最小值，这么是因为0算在正数里，区分为最高位的符号位
而第31行第一列为int的最小值，第二列为int最大值。而第二列的数其实也是2 4 8 16 32 64 128...进制的最大值。
第一列和第二列存在互补关系，也就是说通过~x可以拿到另外一列。
我着重强调好几次，要找规律，规律不就是位移么，你们都是第一列到第二列怎么来的，为什么不考虑怎么从第三列演变成第一列和第二列？
另外虽然第三列一直是-1，但我也说他不是静止的，难道你们都没发现规律？

而问号处，其实可以放4种，+ ^ | ~（但这个~有点限制）,但要考虑为什么会这样子，为什么&不行。这有助于分析什么情况下更适合用什么运算符。

本题的这张图，我不知道你们有没有仔细考虑过，像不像一些网站的相册上切换照片时的特效剪切？第一列从上往下，第二列从下往上？而本题由于是位运算，并且运算方面效率不错，再加上可以指定任意行，所以用来处理图像剪切的特效时是很有用处的。这个大家可以试验下，每次32行，逐行取，并把该剪切窗格布满整个图像，下方放上下一张图片，然后用setclip根据每一行的数字来切窗口，最后只完整的显示下一张图。当然这种方法并不是很好，但你应该试着尝试把所学到的知识加以利用。

//这个足够看出来3种位移方式的区别了
//至于？的运算符，+ ^ |三种都行
for (int shift = 1; shift < Integer.SIZE; shift++)
{
System.out.print(getIntegerToBinary(-1 << shift));
System.out.print(" ? " + getIntegerToBinary(-1 >>> Integer.SIZE - shift));
System.out.println(" = " +getIntegerToBinary(-1 >> shift));
}

复制代码

这里边的 getIntegerToBinary 方法我在第五题的答案里已经写过了，就不在这发占篇幅了。这里有个小知识点，是第五题没有说的，-1 变31 -2变30，用32加上去就行，但局限性很大，不支持32+以后的情况。

for (int shift = 1; shift < Integer.SIZE; shift++)
{
System.out.print(getIntegerToBinary(-1 << shift));
System.out.print(" ? " + getIntegerToBinary(-1 >>> shift));
System.out.println(" = " +getIntegerToBinary(-1 >> shift));
}

复制代码

对比下两个变形，如果根据这个代码的图，第二列不变，而改动第一列应该怎么办？

闾丘日月 · 闾丘日月

第一题第一个反应是
for(int i =1;i<=31;i++)
{ System.out.print(Integer.toBinaryString(-1<<i));
System.out.print(" ? ");
System.out.print(Integer.toBinaryString(~(-1<<i)));
System.out.print(" = ");
System.out.println(Integer.toBinaryString(-1));
}
打印出来类似 11111111111111110 ? 1 = 111111111111111
后来用个subString(00000000000)可以做，不过看到13楼的解法类似，回个帖看第二题了，先不看答案试试。

黑马罗坚 · 黑马罗坚

用1个int类型存放128个数我觉得是不可行的。。。
当你用个int类型的3位当标志位时如标志为001存放1-29 010存放30-58 那么存放{1--32}时存放1-29把1和4-32位填充了1 这时你存放30-32时应该是把标志位2和数据位4-5填充为1把？4和5也已经填充为1了填不填充没区别那么我想问下当你取出来时标志位为001你取出了1-29 标志位为010时你取出的应该是30-58把然而并没有存放33-58啊而且当你在容器里删除1 的话就不说该不该把标志位填充为0 当你把4位清空为0时当其他标志位地4位有数据时是不是也意味着把该标志位的地4位也清空为0了

杨志 · 杨志

嘿嘿！根据第二题的思路想了下，一下是代码：

public class Test12{
//1个int字节全部用来存储,最多用来存32个数
//那么可以提取出其中的3位用来做标识位，那么就最多可以存储 2*2*2 * 29 = 232个数字
//这样就完全可以容纳174个数字的集合
public static void main(String[] args){
int A = 0 ;
int mask = 0 ;
int sign = 5; //这里只需要调出3位就可以标识，故只需要000 到101 就可以，故最大极限为5
for(int shift = 3 ; shift < Integer.SIZE ; shift ++){
mask |= 1 << shift;
}
A = mask | sign ;
System.out.println(getIntegerToBinary(A));
System.out.print("A :");printIntegerSet(A,sign);
}
public static final void printIntegerSet(int set,int sign)
{
StringBuilder sb = new StringBuilder("Set{");
int mask;
for(int i = 0 ; i <= sign ; i ++){
for (int shift = 3; shift < Integer.SIZE; shift++){
mask = 1 << shift;
if(mask == (set & mask))
sb.append(digits[shift-3] + i*29 + ",");
}
sb.deleteCharAt(sb.length() - 1);
} sb.append("}");System.out.println(sb.toString());
}
//取出三位用来做标识位那么就只剩下29位.
public final static int[] digits;
static
{
digits = new int[29];
for (int i = 0; i < 29; i++)
{
digits[i] = i;
}
}
public static final String DEFAULT_INT_ZERO = "00000000000000000000000000000000";
public static final String getIntegerToBinary(int value)
{
String binary = Integer.toBinaryString(value);
int length = Integer.SIZE - binary.length();
return DEFAULT_INT_ZERO.substring(0, length) + binary;
}
}

复制代码

雷云红 · 雷云红

自己试着弄了一下，呵呵感觉不错，但是结果不一样呀。期待楼主跟多技术

刘蕴学 · 刘蕴学

public class Test9
{
public static void main(String[] args)
{
User user = new User();
//这里我们给了用户两个权限，一个注册，一个登陆
//01 | 10 结果是 11，这没什么好说的了，都讲过了
user.setPermission(Permission.BBS_PERMISSION_REGISTER | Permission.BBS_PERMISSION_LOGIN);
System.out.println(getIntegerToBinary(user.getPermission()));
//这里修改了用户的权限，变成了登陆和退出
user.setPermission(Permission.BBS_PERMISSION_LOGIN | Permission.BBS_PERMISSION_LOGOUT);
System.out.println(getIntegerToBinary(user.getPermission()));
//而这，我们给用户增加了一个包括登陆和评论的功能，
//说是回复也行，都一样，但要注意，登陆前边咱已经
//有了吧？这地方就是为什么用　|　，当然你用　＆　＾
//也能行，不过你是不是得求一下补集或者差集呢？　
user.addPermission(Permission.BBS_PERMISSION_LOGIN | Permission.BBS_PERMISSION_COMMENT);
System.out.println(getIntegerToBinary(user.getPermission()));
//删除这里比较有意思，其实就是求两个集合的并集
//并从用户权限集合中把这个并集干掉，就哦拉。
user.deletePermission(Permission.BBS_PERMISSION_LOGIN | Permission.BBS_PERMISSION_ACCESS);
System.out.println(getIntegerToBinary(user.getPermission()));
System.out.println("======================================>");
//这里边列出了查询中会碰到的一些情况，
//也是用来测试这个功能是不是好用
System.out.println(user.contains(Permission.BBS_PERMISSION_COMMENT));
System.out.println(user.contains(Permission.BBS_PERMISSION_LOGOUT));
System.out.println(user.contains(Permission.BBS_PERMISSION_COMMENT | Permission.BBS_PERMISSION_LOGOUT));
System.out.println(user.contains(Permission.BBS_PERMISSION_ACCESS));
System.out.println(user.contains(Permission.BBS_PERMISSION_LOGOUT | Permission.BBS_PERMISSION_ACCESS));
System.out.println("======================================>");
//这个逐级审查其实有个小窍门，只要在找到这个掩码表示的权限之前
//发现1个0，那肯定就是假，至于这个应用在什么地方，方法的注释上有
user.setPermission(Permission.BBS_PERMISSION_REGISTER | Permission.BBS_PERMISSION_LOGIN | Permission.BBS_PERMISSION_COMMENT);
System.out.println(getIntegerToBinary(user.getPermission()));
System.out.println(user.containsBits(Permission.BBS_PERMISSION_COMMENT));
System.out.println(user.containsBits(Permission.BBS_PERMISSION_LOGIN));
System.out.println("======================================>");
user.setPermission(Permission.BBS_PERMISSION_REGISTER | Permission.BBS_PERMISSION_LOGIN | Permission.BBS_PERMISSION_COMMENT | Permission.BBS_PERMISSION_PUBLISH);
System.out.println(getIntegerToBinary(user.getPermission()));
System.out.println(user.containsBits(Permission.BBS_PERMISSION_COMMENT));
System.out.println(user.containsBits(Permission.BBS_PERMISSION_LOGIN));
System.out.println("======================================>");
}
public static final String DEFAULT_INT_ZERO = "00000000000000000000000000000000";
public static final String getIntegerToBinary(int value)
{
String binary = Integer.toBinaryString(value);
int length = Integer.SIZE - binary.length();
return DEFAULT_INT_ZERO.substring(0, length) + binary;
}
}
class User
{
private int permission = 0;
public void setPermission(int permission)
{
this.permission = permission;
}
public int getPermission()
{
return this.permission;
}
/**
* 检查用户是否具有指定的权限集合
* @param masks
* @return
*/
public boolean contains(int masks)
{
// return (this.permission | masks) == this.permission;
return (this.permission & masks) == masks;
}
/**
* 逐级审查
* 这个用在这里其实并不恰当，举个例子说下
* 比如说在10层楼里，很多重要地方都是有权限的吧
* 比如职员只能在1楼，经理可以去2楼，老总在顶楼之类的
* 那么也就是说我有2楼的权限是不是也能去1楼，老总的10层权限
* 哪层都可以吧?
*
* 另外一个是，这个函数的方法是不是最优的，其实还有简便写法
* 你可以自己尝试下。我现在这个写法仅是用来符合逻辑
*
* 从1楼到10检查，比如看你有没有3层的权限，是不是意味着，如果
* 你没有1楼的就直接不可能有3楼的权限，因为你连这个楼的大门都进不来吧？
* 换句话说你想到几楼去，这个楼层之前任何的一层楼你没有权限你都不能到这个楼去
*
* 虽然这个方法的局限性很大，但应用范围也很广
* @param mask
* @return
*/
public boolean containsBits(int mask)
{
//这个0其实会略微影响效率，正常开发不会写这个
//因为0基本上不会有人传进来，这个看似是提高
//效率的办法其实是错的。
if(mask == 0)
return false;
int tmp = 1;
while (true)
{
if((tmp & this.permission) == tmp)
//这个if千万不能合并到上边，否则必错
//因为这里的else的作用域也被提升了
if(tmp == mask)
return true;
else
{
//这里的两行不能写进下边的else里
tmp <<= 1;
continue;
}
else
return false;
}
}
/**
* 为用户添加权限
* @param masks 需要添加的权限集合
*/
public void addPermission(int masks)
{
//这里为什么不用检测是否有某些权限？
this.permission |= masks;
}
/**
* 为用户取消权限
* @param masks 需要取消的权限集合
*/
public void deletePermission(int masks)
{
//这里主要分析的是，用户和你要删除的权限的交集
//用户没有的没必要进行操作
this.permission ^= (this.permission & masks);
}
}
//这里的接口是用来封装掩码集的，其实这在java里很常见
//接口并不意味着必须要有功能抽象
interface Permission
{
public static final int BBS_PERMISSION_REGISTER = 1;
public static final int BBS_PERMISSION_LOGIN = 2;
public static final int BBS_PERMISSION_PUBLISH = 4;
public static final int BBS_PERMISSION_COMMENT = 8;
public static final int BBS_PERMISSION_ACCESS = 16;
public static final int BBS_PERMISSION_LOGOUT = 32;
}

复制代码

刘蕴学 · 刘蕴学

public class Test8
{
public static void main(String[] args)
{
// 1.给定集合A{0,1,2.....30,31}
// 2.给定集合B{5,6....10,11}
// 3.求 A 和 B 的交集
// 4.求 A 和 B 的并集
// 5.求 B 相对于 A 的补集
// 6.求 A 对 B 差集
// 7.求给定集合 C{7,9} 是 A 和 B 哪个集合的子集，并实现任意集合子集的查询功能
// 8.以上所有集合必须使用一个int表示而非数组，所有代码均以按位运算符进行
// 9.使用查表法可以根据int表示的集合正确输出该集合所表示的数组。
// 10.必须详细写出解题思路，实现方法。
//首先考虑，如何使用int来保存一个集合，貌似很难，我们都知道
//int表示的是一个数，表示集合怎么表示？
//先看集合A，0-31，是不是很眼熟？在哪里见过？这不就是int的位移区间么？
//那么是不是可以这样，我们用一个数的位移次数来表示集合？关键是怎么在一个
//数中表示这么多数的位移次数,而且还要保持这个数每一种位移次数的值不重复。
//注意我这里用的mask是java里常见的掩码，shift表示位移，以后看见源文件
//中出现这些变量的名字就知道是做什么的了
//这里边打印了1的不同位移情况下的掩码，我们可以想想，如果我拿没一个掩码
//表示一个数，是不是形成一种映射关系？类似map的key 和 value，那么这个
//key是什么？其实key就是掩码，而这个value就是1到这个掩码的位移次数。
//看这个图是不是眼前一亮，其实跟之前的位移那个图差不多，一个是1，一个是-1
int mask = 0;
for (int shift = 0; shift < 32; shift++)
{
System.out.println(getIntegerToBinary((mask = (1 << shift))));
}
System.out.println("======================================>");
//下面做下尝试，比如我们自己做一个012的集合
//这里我们得想下，一个空集，怎么往里边加数据？前边讲过| ^ + 都行吧，
//其实还是 | 好一些，其他的在某些情况下会有点小问题
int set = 0;
set = set | 1 << 0;
set = set | 1 << 1;
set = set | 1 << 2;
//这里发现我们成功了对么？我们可以用最低位表示这个集合中有0对吧
//而顺序是什么呢？从右往左每一位为1表示有该位位移次数的这个数。
//当然你如果喜欢从左往右也可以，呵呵，自己可以尝试一下
System.out.println(getIntegerToBinary(set));
System.out.println("======================================>");
//1第一点，我们就这么做出来了，B 和 C 的话如法炮制，由于题目里边都是连续的数
//咱就可以投机取巧了
int A = 0, B = 0, C = 0;
for (int shift = 0; shift < Integer.SIZE; shift++)
{
mask = 1 << shift;
//注意这里我为什么要12在前，4在后
if((shift < 12) && (shift > 4))
B |= mask;
if((shift == 7) || (shift == 9))
C |= mask;
A |= mask;
}
System.out.println(getIntegerToBinary(A));
System.out.println(getIntegerToBinary(B));
System.out.println(getIntegerToBinary(C));
System.out.println("======================================>");
//3，求 A 和 B 的交集，这个在Test7里边咱讲了交集用什么？
System.out.println(getIntegerToBinary(A & B));
System.out.println("======================================>");
//4，求 A 和 B 的并集
System.out.println(getIntegerToBinary(A | B));
System.out.println("======================================>");
//5，求 B 相对于 A 的补集
//6，跟 5 一样
System.out.println(getIntegerToBinary(A ^ B));
System.out.println("======================================>");
//7.求给定集合 C{7,9} 是 A 和 B 哪个集合的子集
//这个检查很简单，先求交集，如果这个交集还是他
//自己，那么就是这个集合的子集
System.out.println((C & A) == C);
System.out.println((C & B) == C);
System.out.println("======================================>");
System.out.println(isChid(C, A));
System.out.println(isChid(C, B));
System.out.println("======================================>");
System.out.print("A ");printIntegerSet(A);
System.out.print("B ");printIntegerSet(B);
System.out.print("C ");printIntegerSet(C);
System.out.print("A & B ");printIntegerSet(A & B);
System.out.print("A | B ");printIntegerSet(A | B);
System.out.print("A ^ B ");printIntegerSet(A ^ B);
System.out.print("C & B ");printIntegerSet(C & B);
System.out.print("C | B ");printIntegerSet(C | B);
System.out.print("C ^ B ");printIntegerSet(C ^ B);
}
public static final void printIntegerSet(int set)
{
StringBuilder sb = new StringBuilder("Set{");
int mask;
for (int shift = 0; shift < Integer.SIZE; shift++)
{
mask = 1 << shift;
if(mask == (set & mask))
sb.append(digits[shift] + ",");
}
sb.deleteCharAt(sb.length() - 1);
sb.append("}");
System.out.println(sb.toString());
}
public final static int[] digits;
static
{
digits = new int[Integer.SIZE];
for (int i = 0; i < digits.length; i++)
{
digits[i] = i;
}
}
/**
* 求前一个集合是不是后一个集合的子集
* @return true表示是，false表示不是
*/
public static final boolean isChid(int arg0, int arg1)
{
//子集判断的两种方法，其他位运算符一样可以
//可以自己思考下如何实现
// return arg1 == (arg0 | arg1);
return arg0 == (arg0 & arg1);
}
public static final String DEFAULT_INT_ZERO = "00000000000000000000000000000000";
public static final String getIntegerToBinary(int value)
{
String binary = Integer.toBinaryString(value);
int length = Integer.SIZE - binary.length();
return DEFAULT_INT_ZERO.substring(0, length) + binary;
}
}

复制代码

刘蕴学 · 刘蕴学

本帖最后由刘蕴学于 2012-5-19 02:16 编辑

public class Test7
{
public static void main(String[] args)
{
// & 按位与
//看这行像什么，像逻辑运算符哪里我们写的吧
//0为假，1为真，那么结论就是第四行为1
//而在运算方面，我们可以根据这个规则进行
//逐位运算，即同为1为1，否则为0
System.out.println(0 & 0);
System.out.println(0 & 1);
System.out.println(1 & 0);
System.out.println(1 & 1);
System.out.println("======================================>");
//可以明确的看到只有最后1位都为1吧，结果就是1
System.out.println(getIntegerToBinary(3).substring(24));
System.out.println(getIntegerToBinary(5).substring(24));
System.out.println(getIntegerToBinary(3 & 5).substring(24));
System.out.println("======================================>");
//在观察这个我们发现一点有趣的现象？
System.out.println(getIntegerToBinary(7).substring(24));
System.out.println(getIntegerToBinary(5).substring(24));
System.out.println(getIntegerToBinary(7 & 5).substring(24));
System.out.println("======================================>");
//一排1也就是-1 & 任何数，结果还是他自己
//可以发现所有任意数为1的位都和-1中的该位
//重合
//可以把这个理解成数学中的求交集
System.out.println(getIntegerToBinary(-1));
System.out.println(getIntegerToBinary(1644687));
System.out.println(getIntegerToBinary(-1 & 1644687));
System.out.println("======================================>");
//任何数和0 进行&操作都会得到0，这个操作经常用来清0
//而在数学中，任何集合都不可能和一个空集产生交集
System.out.println(getIntegerToBinary(0));
System.out.println(getIntegerToBinary(1644687));
System.out.println(getIntegerToBinary(0 & 0));
System.out.println("======================================>");
//这里可以看到，0x1f是前边我们讲的拿一个数最后5位，
//而这个0xaaaaaaaa，最后五位01010，前边数据被抛弃
//这里可以很简单的综合上边的结论，0x1f的5位前都是0吧？
//任何数跟0 & 都是0，而后边是不是跟咱们的-1那个很像？
//而这个数跟1排1 & 还是自己吧？
//这个操作我们叫做取指定位
System.out.println(getIntegerToBinary(0x1f));
System.out.println(getIntegerToBinary(0xaaaaaaaa));
System.out.println(getIntegerToBinary(0x1f & 0xaaaaaaaa));
System.out.println("======================================>");
//0xaaaaaaaa 中间的0不太好看拿了多少位，所以用-1
System.out.println(getIntegerToBinary(0xffffffff));
//取后四位
System.out.println(getIntegerToBinary(0xf & 0xffffffff));
//取前四位
System.out.println(getIntegerToBinary(0xf0000000 & 0xffffffff));
//同时取前四位和后四位，至于怎么玩，那是你自己的事情。
//在这里我们用的是16进制，那么16进制表示的是4位2进制位
//表示16进制的1位，所以我们只需要写8位。
//如果觉得16进制的4位有点大，可以考虑用8进制，但是不好用
//一般人都不认识，再说位不是整除的32/3你还少1位，蛋疼
System.out.println(getIntegerToBinary(0xf000000f & 0xffffffff));
System.out.println("======================================>");
// | 按位或
//有一个为1，就为1,看着就懂，不多说
//这个运算符可以当成数学中的求并集
System.out.println(0 | 0);
System.out.println(0 | 1);
System.out.println(1 | 0);
System.out.println(1 | 1);
System.out.println("======================================>");
//可以看到，结果是111，这就是 | 的用法，低3位都有1出现，所以是111
System.out.println(getIntegerToBinary(3).substring(24));
System.out.println(getIntegerToBinary(5).substring(24));
System.out.println(getIntegerToBinary(3 | 5).substring(24));
System.out.println("======================================>");
//有趣的现象又来了，呵呵
System.out.println(getIntegerToBinary(7).substring(24));
System.out.println(getIntegerToBinary(5).substring(24));
System.out.println(getIntegerToBinary(7 | 5).substring(24));
System.out.println("======================================>");
//-1 | 上任何数，结果还是-1，只能说-1这个集合里涵盖了你的任何组合
System.out.println(getIntegerToBinary(-1));
System.out.println(getIntegerToBinary(1644687));
System.out.println(getIntegerToBinary(-1 | 1644687));
System.out.println("======================================>");
//0 | 上任何数，结果还是这个数，这个操作没什么太多实际意义
//但如果是开发中，发现|操作的值没有改变，你首先应该想到|0了
System.out.println(getIntegerToBinary(0));
System.out.println(getIntegerToBinary(1644687));
System.out.println(getIntegerToBinary(0 | 1644687));
System.out.println("======================================>");
//这个你会发现是往上填数据
System.out.println(getIntegerToBinary(0));
System.out.println(getIntegerToBinary(0xf));
//低4位填1
System.out.println(getIntegerToBinary(0 | 0xf));
//高4位填1，这里没写0xf0000000，就是说一下这个数怎么来的
System.out.println(getIntegerToBinary(0 | (0xf << 28)));
//高低四位同时填1 0 | 0xf000000f是一样的
System.out.println(getIntegerToBinary(0 | (0xf | (0xf << 28))));
System.out.println("======================================>");
// ^ 按位异或
//两位不一样为1，一样为假
System.out.println(0 ^ 0);
System.out.println(0 ^ 1);
System.out.println(1 ^ 0);
System.out.println(1 ^ 1);
System.out.println("======================================>");
//有效位的头两位都是不一样的吧，所以最后结果是110
System.out.println(getIntegerToBinary(3).substring(24));
System.out.println(getIntegerToBinary(5).substring(24));
System.out.println(getIntegerToBinary(3 ^ 5).substring(24));
System.out.println("======================================>");
//这个更有趣，有什么发现？好好想想
System.out.println(getIntegerToBinary(7).substring(24));
System.out.println(getIntegerToBinary(5).substring(24));
System.out.println(getIntegerToBinary(7 ^ 5).substring(24));
System.out.println("======================================>");
//这是神马？还没发现么？传说中的取反
System.out.println(getIntegerToBinary(-1));
System.out.println(getIntegerToBinary(1644687));
System.out.println(getIntegerToBinary(-1 ^ 1644687));
//有什么感想？呵呵
System.out.println((-1 ^ 1644687) + 1);
System.out.println("======================================>");
//0 ^ 上任何数，结果还是这个数，这让我们想起来什么了呢？
//跟按位或一样的是吧。
System.out.println(getIntegerToBinary(0));
System.out.println(getIntegerToBinary(1644687));
System.out.println(getIntegerToBinary(0 ^ 1644687));
System.out.println("======================================>");
//按位异或的魅力不止于此，它可以实现局部取反
System.out.println(getIntegerToBinary(0x6ffffff6));
//低4位取反
System.out.println(getIntegerToBinary(0x6ffffff6 ^ 0xf));
//高4位取反
System.out.println(getIntegerToBinary(0x6ffffff6 ^ 0xf0000000));
//高低四位同时取反
System.out.println(getIntegerToBinary(0x6ffffff6 ^ 0xf000000f));
System.out.println("======================================>");
// ~ 取反运算符
// 0变1 1变0
//但跟 ^ 不一样，~是全取反，不能实现局部取反
System.out.println(getIntegerToBinary(0));
System.out.println(getIntegerToBinary(~0));
System.out.println("======================================>");
System.out.println(getIntegerToBinary(1));
System.out.println(getIntegerToBinary(~1));
System.out.println("======================================>");
}
public static final String DEFAULT_INT_ZERO = "00000000000000000000000000000000";
public static final String getIntegerToBinary(int value)
{
String binary = Integer.toBinaryString(value);
int length = Integer.SIZE - binary.length();
return DEFAULT_INT_ZERO.substring(0, length) + binary;
}
}

复制代码

王永旺 · 王永旺

本帖最后由王永旺于 2012-5-18 20:26 编辑

说明自己做的，绝对没有参考上边童鞋的 另：输出方法不是使用的查表法。判断子集的打印方法不太好，暂时没想到更好方法

package cn.wangwang.day2;
/**
* 1. 所有集合均用int对应的二进制每一位表示,1表示该位存在,0表示该位不存在;
* 从右至左依次表示0~31位;
*
* 2. A集合二进制形式为:1111111111111111111111111111111 int类型为:-1
* B集合二进制形式为:0000000000000000000111111100000 int类型位4064
* C集合二进制形式为:0000000000000000000001010000000 int类型位:640
*
* 3. a&b可表示A和B集合的交集
* a|b可表示A和B集合的并集
* a^b可表示B相对于 A的补集
* ~（a^b）可表示 A 对 B 差集
*
* 4.判断Ｃ集合是否为Ａ子集可看其是否有交集，没有则判定不是子集。
*/
public class abc {
public static void main(String[] args) {
int a = -1;
int b = 4064;
int c = 640;
int and = a&b; //and表示A和B集合的交集
int or = a|b; //or表示A和B集合的并集
int xor=a^b ; //xor表示B相对于 A的补集
int eor=~xor; //eor表示 A 对 B 差集
System.out.println("Ａ与Ｂ交集为:"); myPrint(and); //myPrint用于将结果打印
System.out.println("Ａ与Ｂ并集为:"); myPrint(or);
System.out.println("Ａ与Ｂ补集为:"); myPrint(xor);
System.out.println("Ａ与Ｂ差集为:"); myPrint(eor);
isSubArray(a,c); //判断是否为a子集。
isSubArray(b,c); //判断是否为b子集。
}
//下面为打印方法
private static void myPrint(int value) {
boolean haveHigh=false; //是否有最高位.
if(value<0){
haveHigh=true;
value=value&2147483647; //最高位设为0
}
System.out.print("["); //逐位打印
for(int i=0;i<31;i++){
if(value%2==1)
System.out.print(i+" ");
value=value/2;
}
if(haveHigh) //是否输出最高位
System.out.print(31);
System.out.println("]");
}
//下面为判断子集的方法
private static void isSubArray(int a, int c) {
if((c&a)!=0){
System.out.println("集合"+Integer.toBinaryString(c)+"是集合"+Integer.toBinaryString(a)+"的子集");
} else
System.out.println("集合"+Integer.toBinaryString(c)+"不是集合"+Integer.toBinaryString(a)+"的子集");
}
}

复制代码

黑马罗坚 · 黑马罗坚

package aa;

/**
* 第二个，集合
*1.给定集合A{0,1,2.....30,31}
*2.给定集合B{5,6....10,11}
*3.求 A 和 B 的交集
*4.求 A 和 B 的并集
*5.求 B 相对于 A 的补集
*6.求 A 对 B 差集
*7.求给定集合 C{7,9} 是 A 和 B 哪个集合的子集，并实现任意集合子集的查询功能
*8.以上所有集合必须使用一个int表示而非数组，所有代码均以按位运算符进行
*9.使用查表法可以根据int表示的集合正确输出该集合所表示的数组。
*10.必须详细写出解题思路，实现方法。去工作之后，你写的代码不是给你自己看的，是给别人看的，你不写设计思路，不写注释，你让人怎么看？
*
*思路 int变量的每位分别代表1到31个元素  由于这里只有0到31所以最低为代表0 最高位代表31 当那为为1代表这个集合里有这个数
*为0代表集合里没这个数
*集合A用int变量listA表示的话为每位都是1所以为-1
*集合B用int变量listB表示的话为5到11位
*求A和B的交际就是listA&listB的结果位数为1的就是交际
*/
public class MyListDemo {
public static void main(String[] args) {
int listA=-1;
//集合b是5到11 所以我拿12位表示它  因为重0开始由于这个集合头前五位是0
//地6为到12为1 用16进制表示为0xfe0我拿这个数|上0就是我要的数了
int listB=0|0xfe0;
//求listA与listB的交际拿listA&上listB 定义一个int型变量存储交集
int jiaoJi=listA&listB;
//应为是交际而listB的元素是5到11所以取出6到12位中改位为1的数在-1即可
System.out.println("交集为:");
get(jiaoJi,6,12);
int bingJi=listA|listB;
//并集拿2个集合代表的数进行或运算就可以了  次数为大的集合1到32
System.out.println("并集为:");
get(bingJi,1,32);
System.out.println("补集为:");
//补集listA有的listB没有 ^是2进制位相同为0不同为1 应为listA所有位都是1所以不会
//出现listB有的listA没有
int buJi=listA^listB;
get(buJi,1,32);
//求给定集合 C{7,9} 是 A 和 B 哪个集合的子集
//先创建个c集合  每个16进制位代表4位
//集合c和集合A,B&操作 8到10位为1那么就是它的子集
int listC=0|0x380;
if (contains(listC&listA,8,10)){
System.out.println("listC是listA的子集");
}
if (contains(listC&listB,8,10)){
System.out.println("listC是listB的子集");
}

// System.out.println(Integer.toBinaryString());
}
/**
   * @param list
   * @param start
   * @param end
   * @return
   */
static boolean contains(int list,int start,int end){
boolean flag=false;
if(get(list,start,end,true)){
flag=true;
}
return flag;

}
/**
   * 把int集合所带表的集合的元素循环拿出来
   * 从list集合里面的指针为start-1处开始check匹配到end处当符合要求就打印出来
   * flag 为true的话就不打印当匹配不成功的话就把ret设置为false退出循环换回ret
   */
static boolean get(int list,int start,int end,boolean flag){
boolean ret=false;
int arg=(start/start)<<start-1;
for(int row=start;row<=end;row++){
if(check(list,arg)){
if(flag){
arg<<=1;
ret=true;
continue;
}
System.out.print(row-1+" ");
}
if(flag){
ret=false;
break;
}
arg<<=1;
// System.out.println(arg);
}
return ret;
}
/**
   * 打印集合中的数
   */
static void get(int list,int start,int end){
get(list,start,end,false);
//没打印完一个空行一次
System.out.println();
}
   /**
   * 用于检测元素是否存在
   * 判断该位是否有元素只需要用那位为1其他未为0的数&int集合在看结果是否等于&操作的数
   */
static boolean check(int list,int arg){
boolean flag=false;
list=list&arg;
if(list==arg){
flag=true;
// System.out.println(list==arg);
}
return flag;
}
}

xieshuhua · xieshuhua

帮忙总结下大家解决问题的思路。
1、先把十进制的A、B、C分别按照<<、~和|循环32遍全部表示出来，再通过 Integer.toBinaryString打印出来。
2、加入一个31个0的字符串，放在B前，每次if循环字符串减少一个0.
另：我想玄机就在这个31位0的字符串吧，只有完全不用字符串才算是完成了整个题目，不知道是不是这样。

马浩 · 马浩

class Lesson3
{
public static void main(String []args)
{
int x=-1;
int y=31;
for (int i=1;i<32 ;i++ )
{
int a=x<<i;

int b=-1^a;
x=-1;
int sum=a|b;

String s="00000000000000000000000000000000";

System.out.println(Integer.toBinaryString(a)+"|"+s.substring(0,y--)+Integer.toBinaryString(b)+"="+Integer.toBinaryString(sum));

}
}

}

高云飞 · 高云飞

本帖最后由高云飞于 2012-5-17 17:08 编辑

            int a = 1;
            int b = ~a;
            StringBuffer zeros = new StringBuffer ("00000000000000000000000000000000");
            for (int i = 0; i < 31; i++) {
                     System.out.println(Integer.toBinaryString(b) + "^" + zeros.substring(i+1) +  Integer.toBinaryString(a) + "=" + Integer.toBinaryString(a^b));
                     b = b << 1;
                     a = (a << 1) + 1;
            }
终于用这种方式实现格式与题目一致了，本来想用格式控制字符串的，发现，实现起来太难了，没有实现的了。就用这种方法了。

徐然 · 徐然

这样行不，求详解

class Test
{
public static void main(String[] args)
{
String s = "00000000000000000000000000000000";
int count = 1;
      for(long x=-2;x>=-2147483648;)
      {
         System.out.println(Integer.toBinaryString((int)(x))+"+"+
            s.substring(count)+Integer.toBinaryString((int)(~x))+"="+
            Integer.toBinaryString((int)(~x+x)));
                  x=x*2 ;
                  count++;
      }
}
}

黄奕豪 · 黄奕豪

本帖最后由黄奕豪于 2012-5-17 14:49 编辑

黄奕豪发表于 2012-5-17 12:39
？可以用^表示，代码如下，可是就是不知道怎么把正数的前面0补足！先上代码

在网上查了一下，加上第二个数 ...

:L我只学到了毕老师Java基础的第十天，也只能用最土的方法写出来了！！具体算法是，第一个数据循环每次向左移计数器i位（head<<i），第二个数据每次向左移一位然后加上1再赋值回给原数据（end=(end<<1)+1）得到进入后面异或的第二个数字,然后利用最后得到的两个数字异或得到最后一个数字！！是我的代码阅读性太差了！！555555

黑马罗坚 · 黑马罗坚

我确实想不出该怎么用不用字符串把头前的0打出来。。既然要用字符串还是StringBuilder的deleteCharAt()方法效率高点还忘你指点下怎么不用字符串把头前的0打印出来难道搞一个函数打印一个0 调用这个函数（31-row)次？

黑马罗坚 · 黑马罗坚

public class Demo {
public static void main(String[] args) {
int i=-1;
StringBuilder ling=new StringBuilder("0000000000000000000000000000000");
for(int row=1;row<=31;row++){
i=i<<1;
int sum=i|~i;
System.out.println(Integer.toBinaryString(i)+
"?"+ling+Integer.toBinaryString(~i)+"="+
Integer.toBinaryString(sum));
ling.deleteCharAt(0);
}
}
}

徐然 · 徐然

徐然发表于 2012-5-17 13:01
都被楼主带坑里了吧，其实很简单，我这就是正解
这题就考一点，类型转换 ...

额~~表打击我撒~~~我在论坛一直是被打击对象，虽然没人认识我，但是看大家的问题和回答我就倍受打击了
好不容易有次独立思考的机会，额~~~算了我还是回家种地把

王永旺 · 王永旺

话说只能搞成这样了

public class NUM {
public static void main(String[] args) {
int a =-1;
String s= "00000000000000000000000000000000" ;
for (int i =1;i<32; i++) {
a=a<<1;
System.out.println(Integer.toBinaryString(a)+" ^ "
+s.substring(i)+Integer.toBinaryString(~a)+" = "
+Integer.toBinaryString(a+~a));
}
}
}

复制代码

李月 · 李月

public class yiwei {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

int x=1;
int i=-1;
String s="0000000000000000000000000000000";
for(int n=30;n>=0;n--)
{
i=i<<1;
System.out.print(Integer.toBinaryString(i)+"|"+s.substring(0,n+1)+Integer.toBinaryString(x)+"=");

System.out.println(Integer.toBinaryString(i|x));

x=x<<1|1;

}

}

}

我又改了，这回不少个1了。

帐号		自动登录	找回密码
密码			加入黑马

【送分】第六题位运算完

评分

29 个回复

点评

评分

点评

评分

评分

评分

点评

评分

点评

评分

点评

评分

点评

点评

点评

评分

点评

点评

评分

点评

评分

黑马骑士勋章

【送分】第六题 位运算 完

评分

29 个回复

点评

评分

点评

评分

评分

评分

点评

评分

点评

评分

点评

评分

点评

点评

点评

评分

点评

点评

评分

点评

评分

黑马骑士勋章

【送分】第六题位运算完