Bitwise and Bit Shift Operators

位运算Bitwise:

位运算符包括:　与（&）、非（~）、或（|）、异或（^）

　　&：当两边操作数的位同时为1时，结果为1，否则为0。如1100&1010=1000

      | ：当两边操作数的位有一边为1时，结果为1，否则为0。如1100|1010=1110

      ~：0变1,1变0

      ^：两边的位不同时，结果为1，否则为0.如1100^1010=0110

位运算与位移动运行符的一个场景:

    HashMap的功能是通过“键(key)”能够快速的找到“值”。下面我们分析下HashMap存数据的基本流程：
    1、 当调用put(key,value)时，首先获取key的hashcode，int hash = key.hashCode();
    2、 再把hash通过一下运算得到一个int h.
hash ^= (hash >>> 20) ^ (hash >>> 12);
int h = hash ^ (hash >>> 7) ^ (hash >>> 4);
为什么要经过这样的运算呢？这就是HashMap的高明之处。先看个例子，一个十进制数32768(二进制1000 0000 0000 0000)，经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗？或许这样还看不出什么，再举个数字61440(二进制1111 0000 0000 0000)，运算结果是65263(二进制1111 1110 1110 1111)，现在应该很明显了，它的目的是让“1”变的均匀一点，散列的本意就是要尽量均匀分布。

  3、 得到h之后，把h与HashMap的承载量（HashMap的默认承载量length是16，可以自动变长。在构造HashMap的时候也可以指定一个长 度。这个承载量就是上图所描述的数组的长度。）进行逻辑与运算，即 h & (length-1)，这样得到的结果就是一个比length小的正数，我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的 位置。第2步那个算法的意义就是希望能够得出均匀的index，这是HashTable的改进，HashTable中的算法只是把key的 hashcode与length相除取余，即hash % length，这样有可能会造成index分布不均匀。还有一点需要说明，HashMap的键可以为null，它的值是放在数组的第一个位置。

4、 我们用table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素（这个元素是HashMap内部定义的一个类Entity， 基本结构它包含三个类，key，value和指向下一个Entity的next）,没有的话就创建一个Entity对象，在 table[index]位置上插入，这样插入结束；如果有的话，通过链表的遍历方式去逐个遍历，看看有没有已经存在的key，有的话用新的value替 换老的value；如果没有，则在table[index]插入该Entity，把原来在table[index]位置上的Entity赋值给新的 Entity的next，这样插入结束。

移位运算符Bit Shift Operators

java移位运算符不外乎就这三种：<<（左移）、>>（带符号右移）和>>>（无符号右移）。 
1、 左移运算符
左移运算符<<使指定值的所有位都左移规定的次数。
1）它的通用格式如下所示：
value << num
num 指定要移位值value 移动的位数。
左移的规则只记住一点：丢弃最高位，0补最低位
如果移动的位数超过了该类型的最大位数，那么编译器会对移动的位数取模。如对int型移动33位，实际上只移动了33%32=1位。

2）运算规则
按二进制形式把所有的数字向左移动对应的位数，高位移出(舍弃)，低位的空位补零。
当左移的运算数是int 类型时，每移动1位它的第31位就要被移出并且丢弃；
当左移的运算数是long 类型时，每移动1位它的第63位就要被移出并且丢弃。
当左移的运算数是byte 和short类型时，将自动把这些类型扩大为 int 型。

3）数学意义
在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方

4）计算过程：
例如：3 <<2(3为int型)
1）把3转换为二进制数字0000 0000 0000 0000 0000 0000 0000 0011，
2）把该数字高位(左侧)的两个零移出，其他的数字都朝左平移2位，
3）在低位(右侧)的两个空位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 1100，
转换为十进制是12。
移动的位数超过了该类型的最大位数，
如果移进高阶位（31或63位），那么该值将变为负值。下面的程序说明了这一点：

// Left shifting as a quick way to multiply by 2.
public class MultByTwo {
public static void main(String args[]) {
   int i;
   int num = 0xFFFFFFE; 
   for(i=0; i<4; i++) {
       num = num << 1; 
     System.out.println(num); } }}

该程序的输出如下所示：

536870908
1073741816
2147483632
-32
注：n位二进制，最高位为符号位，因此表示的数值范围-2^(n-1) ——2^(n-1) -1,所以模为2^(n-1)。

2、 右移运算符(带符号)
    public static void main(String args[]) {
           int i;
           int num = 0b11111111101111111111000000000000;
           System.out.println(name(num) + "  " + num);
           for(i=0; i<25; i++) {
               num = num >> 1; //最高位（符号位为1时负数），右移补充的数都是1    （符号位为0时正数），右移补充的数都是0 
               System.out.println(name(num) + "  " + num);           
           } }    
    public static String name(int num) {
        String tmp = Integer.toBinaryString(num);
        while(tmp.length() < 32){
            tmp = "0" + tmp;
        }
        return tmp;
    }

输出结果（负数时）
11111111101111111111000000000000  -4198400
11111111110111111111100000000000  -2099200
11111111111011111111110000000000  -1049600
11111111111101111111111000000000  -524800
11111111111110111111111100000000  -262400
11111111111111011111111110000000  -131200
11111111111111101111111111000000  -65600
11111111111111110111111111100000  -32800
11111111111111111011111111110000  -16400
11111111111111111101111111111000  -8200
11111111111111111110111111111100  -4100
11111111111111111111011111111110  -2050
11111111111111111111101111111111  -1025
11111111111111111111110111111111  -513
11111111111111111111111011111111  -257
11111111111111111111111101111111  -129
11111111111111111111111110111111  -65
11111111111111111111111111011111  -33
11111111111111111111111111101111  -17
11111111111111111111111111110111  -9
11111111111111111111111111111011  -5
11111111111111111111111111111101  -3
11111111111111111111111111111110  -2
11111111111111111111111111111111  -1
11111111111111111111111111111111  -1
输出结果（正数时）
01111111101111111111000000000000  2143285248
00111111110111111111100000000000  1071642624
00011111111011111111110000000000  535821312
00001111111101111111111000000000  267910656
00000111111110111111111100000000  133955328
00000011111111011111111110000000  66977664
00000001111111101111111111000000  33488832
00000000111111110111111111100000  16744416
00000000011111111011111111110000  8372208
00000000001111111101111111111000  4186104
00000000000111111110111111111100  2093052
00000000000011111111011111111110  1046526
00000000000001111111101111111111  523263
00000000000000111111110111111111  261631
00000000000000011111111011111111  130815
00000000000000001111111101111111  65407
00000000000000000111111110111111  32703
00000000000000000011111111011111  16351
00000000000000000001111111101111  8175
00000000000000000000111111110111  4087
00000000000000000000011111111011  2043
00000000000000000000001111111101  1021
00000000000000000000000111111110  510
00000000000000000000000011111111  255
00000000000000000000000001111111  127
00000000000000000000000000111111  63
00000000000000000000000000011111  31
00000000000000000000000000001111  15
00000000000000000000000000000111  7
00000000000000000000000000000011  3
00000000000000000000000000000001  1
00000000000000000000000000000000  0
00000000000000000000000000000000  0


3、无符号右移 忽略了符号位扩展，0补最高位

11111111101111111111000000000000  -4198400
01111111110111111111100000000000  2145384448
00111111111011111111110000000000  1072692224
00011111111101111111111000000000  536346112
00001111111110111111111100000000  268173056
00000111111111011111111110000000  134086528
00000011111111101111111111000000  67043264
00000001111111110111111111100000  33521632
00000000111111111011111111110000  16760816
00000000011111111101111111111000  8380408
00000000001111111110111111111100  4190204
00000000000111111111011111111110  2095102
00000000000011111111101111111111  1047551
00000000000001111111110111111111  523775
00000000000000111111111011111111  261887
00000000000000011111111101111111  130943
00000000000000001111111110111111  65471
00000000000000000111111111011111  32735
00000000000000000011111111101111  16367
00000000000000000001111111110111  8183
00000000000000000000111111111011  4091
00000000000000000000011111111101  2045
00000000000000000000001111111110  1022
00000000000000000000000111111111  511
00000000000000000000000011111111  255
00000000000000000000000001111111  127
00000000000000000000000000111111  63
00000000000000000000000000011111  31
00000000000000000000000000001111  15
00000000000000000000000000000111  7
00000000000000000000000000000011  3
00000000000000000000000000000001  1
00000000000000000000000000000000  0
00000000000000000000000000000000  0