刷LeetCode的一道题，联想到Bloom Filter和Redis的BitMap，有感而发。

用二进制的原因有两点，一是因为计算机中数据本身就是二进制存储的，运行起来快；二是因为省空间。

位运算

符号 描述 规则
& 与 两个为1才出1，有0出0
| 或 一个有1就出1
^ 异或 两个相同为0，不同为1
~ 取反 0变1，1变0
<< 左移 全部向左移动，高位丢弃，低位补0
>> 右移 全部向右移动，高位补0，低位丢弃（对于有符号数另外处理）

注：二进制中左边是高位，右边是低位

常用的位运算技巧

  1. // 判断一个数的奇偶
  2. // 因为一个数只要是奇数,那么它的二进制低位就是1，1&1自然就是1，反之就是偶数
  3. x & 1 == 1
  5. // 清除最低位的1
  6. // 根据&的规则，有0出0
  7. x & (x-1) 
  9. // 如何找出出现一次的数，只有一个数字出现了一次，其余数字都出现了两次
  10. x = x ^ x1 ^ x1 ^ x3 ^ x3

LeetCode题目

输入一个数判断二进制1的数量

  1. public int hammingWeight(int n) {
  2.         int count = 0;
  3.         while (n != 0){
  4.             // 清除最低位的1
  5.             n = n & (n-1);
  6.             count ++;
  7.         }
  8.         return count;
  9.     }