位运算与Hash
1.位运算
1.在计算机系统中，数字⼀律⽤补码表⽰、运算和存储。
原码：原码表⽰法在数字前⾯增加了⼀位符号位，即最⾼位为符号位，正数位该位为0，负数位该位为1.⽐如⼗进制的5如果⽤8个⼆进制位来表⽰就是00000101，-5就是10000101。 反码：正数的反码是其本⾝，负数的反码在其原码的基础上，符号位不变，其余各个位取反。5的反码就是00000101，⽽-5的则为11111010。
补码：正数的补码是其本⾝，负数的补码在其原码的基础上，符号位不变，其余各位取反，最后+1。即在反码的基础上+1。5的反码就是00000101，⽽-5的则为11111011。
1.2 为什么计算机系统中，数字⽤补码表⽰
计算机保存最原始的数字，也是没有正和负的数字，叫没符号数字
如果我们在内存分配4位（bit）去存放⽆符号数字，是下⾯这样⼦的
为了表⽰正与负，⼈们发明了"原码"，把⽣活应该有的正负概念，原原本本的表⽰出来
把左边第⼀位腾出位置，存放符号，正⽤0来表⽰，负⽤1来表⽰
但使⽤“原码”储存的⽅式，⽅便了看的⼈类，却苦了计算机
我们希望 （+1）和（-1）相加是0，但计算机只能算出0001+1001=1010 (-2)
这不是我们想要的结果 (╯’ - ')╯︵ ┻━┻
另外⼀个问题，这⾥有⼀个（+0）和（-0）
北大校花李莹为了解决“正负相加等于0”的问题，在“原码”的基础上，⼈们发明了“反码”
“反码”表⽰⽅式是⽤来处理负数的，符号位置不变，其余位置相反
当“原码”变成“反码”时，完美的解决了“正负相加等于0”的问题
过去的（+1）和（-1）相加，变成了0001+1101=1111，刚好反码表⽰⽅式中，1111象征-0
⼈们总是进益求精，历史遗留下来的问题—— 有两个零存在，+0 和 -0
我们希望只有⼀个0，所以发明了 补码，同样是针对"负数"做处理的
"补码"的意思是，从原来"反码"的基础上，补充⼀个新的代码，（+1）
我们的⽬标是，没有蛀⽛（-0）
有得必有失，在补⼀位1的时候，要丢掉最⾼位
我们要处理"反码"中的"-0"，当1111再补上⼀个1之后，变成了10000，丢掉最⾼位就是0000，刚好和左边正数的0，完美融合掉了
这样就解决了+0和-0同时存在的问题
另外"正负数相加等于0"的问题，同样得到满⾜
举例，3和（-3）相加，0011 + 1101 =10000，丢掉最⾼位，就是0000（0）
同样有失必有得，我们失去了(-0) , 收获了（-8）
以上就是"补码"的存在⽅式
结论：保存正负数，不断改进⽅案后，选择了最好的补码⽅案
1.3 位运算使⽤
位操作只能⽤于整型，对于float或double，编译器会报错。
位运算的运算符优先级较低
内窥镜检查位运算都是对于补码来说，操作的是负数，则必须转换为对应的补码进⾏操作
细化符号描述运算规则
门诊
按位运算&与两位都为1，那么结果为1
|或有⼀位为1，那么结果为1
~⾮~0 = 1,~1 = 0
^异或两位不相同，结果为1
移位运算<<；左移各⼆进制位全部左移N位，⾼位丢弃，低位补0
>>右移各⼆进制位全部右移N位，若值为正，则在⾼位插⼊ 0，若值为负，则在⾼位插⼊ 1
>>>⽆符号右移各⼆进制位全部右移N位，⽆论正负，都在⾼位插⼊0
1.4 位运算的常⽤⼩技巧
1.4.1 判断奇偶数
通过与运算判断奇偶数，伪代码如下：
n&1 == 1?”奇数”:”偶数”
奇数最低位肯定是1，⽽1的⼆进制最低位也是1，其他位都是0，所以所有奇数和1与运算结果肯定是1。
在⼀个系统中，⽤户⼀般有查询(Select)、新增(Insert)、修改(Update)、删除(Delete)四种权限，四种权限有多种组合⽅式，也就是有16中不同的权限状态（2的4次⽅）。
Permission
国民生产总值平减指数⼀般情况下会想到⽤四个boolean类型变量来保存：
public class Permission {
// 是否允许查询
private boolean allowSelect;
// 是否允许新增
private boolean allowInsert;
// 是否允许删除
private boolean allowDelete;
// 是否允许更新
private boolean allowUpdate;
/
/ 省略Getter和Setter
}
上⾯⽤四个boolean类型变量来保存每种权限状态。
NewPermission
下⾯是另外⼀种⽅式，使⽤位掩码的话，⽤⼀个⼆进制数即可，每⼀位来表⽰⼀种权限，0表⽰⽆权限，1表⽰有权限。
public class NewPermission {
// 是否允许查询，⼆进制第1位，0表⽰否，1表⽰是
public static final int ALLOW_SELECT =1<<0;// 0001
// 是否允许新增，⼆进制第2位，0表⽰否，1表⽰是
public static final int ALLOW_INSERT =1<<1;// 0010
// 是否允许修改，⼆进制第3位，0表⽰否，1表⽰是
public static final int ALLOW_UPDATE =1<<2;// 0100
// 是否允许删除，⼆进制第4位，0表⽰否，1表⽰是
public static final int ALLOW_DELETE =1<<3;// 1000
// 存储⽬前的权限状态
private int flag;
/**
* 重新设置权限职教通讯
*/
public void setPermission(int permission){
flag = permission;
}
/
**
* 添加⼀项或多项权限
*/
public void enable(int permission){
flag |= permission;
}
/**
* 删除⼀项或多项权限
*/
public void disable(int permission){
flag &=~permission;
}
/**
* 是否拥某些权限
*/
public boolean isAllow(int permission){
return(flag & permission)== permission;
}
/**
* 是否禁⽤了某些权限
*/
public boolean isNotAllow(int permission){
return(flag & permission)==0;
}
/**
* 是否仅仅拥有某些权限
*/
public boolean isOnlyAllow(int permission){
return flag == permission;
}
}
以上代码中，⽤四个常量表⽰了每个⼆进制位代码的权限项。例如：
ALLOW_SELECT = 1 << 0 转成⼆进制就是0001，⼆进制第⼀位表⽰Select权限。
ALLOW_INSERT = 1 << 1 转成⼆进制就是0010，⼆进制第⼆位表⽰Insert权限。
private int flag存储了各种权限的启⽤和停⽤状态，相当于代替了Permission中的四个boolean类型的变量。
⽤flag的四个⼆进制位来表⽰四种权限的状态，每⼀位的0和1代表⼀项权限的启⽤和停⽤，下⾯列举了部分状态表⽰的权限：
使⽤位掩码的⽅式，只需要⽤⼀个⼤于或等于0且⼩于16的整数即可表⽰所有的16种权限的状态。
此外，还有很多设置权限和判断权限的⽅法，需要⽤到位运算，例如：
public void enable(int permission){
flag |= permission;// 相当于flag = flag | permission;远程传输
}
调⽤这个⽅法可以在现有的权限基础上添加⼀项或多项权限。
添加⼀项Update权限：
假设现有权限只有Select，也就是flag是0001。执⾏以上代码，flag = 0001 | 0100，也就是0101，便拥有了Select和Update两项权限。
添加Insert、Update、Delete三项权限：
| NewPermission.ALLOW_UPDATE | NewPermission.ALLOW_DELETE);
NewPermission.ALLOW_INSERT | NewPermission.ALLOW_UPDATE | NewPermission.ALLOW_DELETE运算结果是1110。假设现有权限只有Select，也就是flag是0001。flag = 0001 | 1110，也就是1111，便拥有了这四项权限，相当于添加了三项权限。
上⾯的设置如果使⽤最初的Permission类的话，就需要下⾯三⾏代码：
permission.setAllowInsert(true);
permission.setAllowUpdate(true);
permission.setAllowDelete(true);
⼆者对⽐
设置仅允许Select和Insert权限
Permission
permission.setAllowSelect(true);
permission.setAllowInsert(true);
permission.setAllowUpdate(false);
permission.setAllowDelete(false);
NewPermission
permission.setPermission(NewPermission.ALLOW_SELECT | NewPermission.ALLOW_INSERT);
判断是否允许Select和Insert、Update权限
Permission
if(permission.isAllowSelect()&& permission.isAllowInsert()&& permission.isAllowUpdate())
NewPermission
if(permission. isAllow (NewPermission.ALLOW_SELECT
| NewPermission.ALLOW_INSERT | NewPermission.ALLOW_UPDATE))
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议