本文是对近期二进制专题的leetcde习题的复盘。文中的解决思路来源于leetcode的讨论，以及一些网页。 342 判断一个整数(32bits)是否是4的次幂。 写出 4i,i=0,1,2,3,4... 的二进制表示，查找规律。会发现这些数的特征是 a 都>0；b 只有一位是1，代码：n&(n-1)==0；c 1都在奇数位置，如果从1开始数，代码：n&(0x55555555)!=0。
191 数数一个无符号整数n的二进制表示中有几个1。 方法一：每次判断最末位置是否为1：n&1==1=>最末位是1；接着n=n>>1,继续判断。 方法二：每次判断n的某一个位置，从最末位开始。n&1!=0=>该位是1；接着计算(n&(1<<1))，再继续n&(1<<2)，如此下午，判断32个位置。方法一和二思路是相同的，都是通过位移来判断不同的位置，都需要32次循环，只是一个移动数字，一个移动掩码mask。 方法三：如果数字n的二进制位只有1位是1，循环32次太浪费了。n&(n-1) 实际上是把一个数的最低位的有效1，给去掉了；而且一次还只能去掉一个位置上的1。这样只要n=(n&(n-1))，n不等于0，就知道1的位数是加1的。 思考：如果是有符号的呢？
136 Single Number。给定的数组中，每个数都出现了两次，只有一个数出现了一次。找到只出现了一次的数。 方法：两个相同的数异或之后会是0。所有数字异或之后加和，留下的数就是要找的数。
461 Hamming Distance。海明距离是计算两个int，都多少个位是不同的。 方法：任意两个数异或之后不同的位会变为1。步骤是：n=(i^j)；数n有几个1，等同于191。 169 Majority Element. 主元素是指在数组中出现次数超过n/2的元素。前提假设：数组不为空；主元素总数存在。(这题做过，怎么一点印象都没有) 方法1：循环计算nums[i]出现次数。时间复杂度 O(n2) 。 方法2：用hashmap，保存每个数字出现次数。时间复杂度 O(n) ，空间复杂度 O(n) 。 方法3：先排序，再找到最长的连续串。时间复杂度 O(nlogn) 。 方法4：分治法，数组一分为2，查找第一部分的主元素A，第二部分的主元素B。如果A的次数=B的次数，A和B都是候选主元素。如果不同，则选出主元素。时间复杂度 O(nlogn) 。 方法5：随机选元素（不甚理解）。平均时间复杂度 O(n) ，最坏是无穷。随机啊。。。。 方法6：Moore Voting algorithm。定义候选元素element和次数count。不断遍历nums，如果count=0，element=当前元素，count=1；如果count>0，当前元素=element则count++；否则count–。留下的element一定是主元素。时间复杂度 O(n) 。这个想法太奇妙了。有点像双方交战，主元素是一方，其他元素是一方。不断增加或者减少count。 方法7：位运算。直接上代码吧。有点不会描述了。一个int，32位。哪个位置上1的个数>n/2，那这一位一定是主元素贡献的。所以只要找到1出现次数超过n/2的位，其他位置为0，就可以找到主元素。
public int majorityElement(int[] nums) { int[] bit = new int[32]; for (int i = 0; i < nums.length; i++) { for (int j = 0; j < 32; j++) { bit[j] += (nums[i] >> j) & 1; } } int majority = 0; for (int j = 0; j < 32; j++) { bit[j] = bit[j] > (nums.length / 2)? 1 : 0; majority += bit[j] << j; } return majority; }405 将一个整数用十六进制表示 方法：做十进制与十六进制基础元素的映射。做映射有两种方式，一种是map，一种是数组。当key是数字的时候用数组还是比较方便的。nums[]={0,1,2,….a,b,…f}。数组的下标正好是十六进制对应的十进制。 接着十六进制可以用4位二进制表示。每次将num与0x0f做与操作，这样就能只留下最后四位了。
public String toHex(int num) { if(num==0) return "0"; char[] hexadecimalChar = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' }; String r = ""; while (num != 0) { r = hexadecimalChar[num & 0x0f] + r; num >>>= 4; } return r; }190 给定一个无符号的整数num，输出一个整数out，这个整数是输入数字的二进制的逆转。如果方法要多次调用，可以怎么优化。 方法一：变量r为最后结果，从num低位开始，每次处理1位，r<<1+最低位处理的值。循环32次。
public int reverseBits(int n) { int result = 0; for (int i = 0; i < 32; i++) { result <<= 1; result += n&1; n >>>=1; } return result; }多次调用优化的方法应该是存储字节与结果的映射关系。 方法二：可以先看代码。来自网页。每4位当做一个整体处理，int32位分为8个部分：abcdefgh。处理顺序是：abcdefgh -> efghabcd -> ghefcdab -> hgfedcba。代码最后两行是处理：4位内部的倒序。 这思路看到后真是震惊。原来分治法还能这么玩。膜拜啊。
public int reverseBits(int n) { n = (n >>> 16) | (n << 16); n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8); n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4); n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2); n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1); return n; }476 Number Complement。一个int的补是指二进制取反。但是高位的0不变。例如5的补是2。因为 5=101 ，取反，010=2。但是一个int有32位，对于5，从第4位开始的0都不算。所以需要知道最高位的1，在哪个位置即可。 下面是两种解法。
public int findComplement(int num) { return ~num & (Integer.highestOneBit(num) - 1); } public int findComplement2(int num) { int mask = Integer.MAX_VALUE; while((num & mask) !=0){ mask <<=1; } System.out.println(~mask); return ~num & (~mask); }401 Binary Watch。二进制手表。好酷的手表。这是一个穷举搜索的问题。 时：8 4 2 1 。每一个选与不选分别用1和0 表示。这样就形成了一个一个的二进制数。如果说时钟只有一个灯亮，那么选择可能有： 时：8 4 2 1 f1: 0 0 0 1 f2: 0 0 1 0 f3: 0 1 0 0 f4: 1 0 0 0
231 判断一个数是否是2的平方。2的平方的特征是：a 大于0；2 只有一个1。
public boolean isPowerOfTwo(int n) { return n>0 && (n&(n-1))==0; }389 Find the Difference。输入两个字符串s、t。t是s中所有字母随机排列后组成的字符串，但是t中有一个字符在s中没有出现。找出在t中没有出现的那个字符。 思路一：用map。遍历s中每个字符的出现次数，保存在map中。接着遍历t中的字符串，将map[key]value值减1。如果在map的key值不存在或者说map[key]的value <=0 ，那这个字符一定不在s中出现。 思路2：位操作。用异或可以将相同的字符抵消。s和t两个字符串做异或，留下的就是没在s中出现的字符。
public char findTheDifference2(String s, String t) { char ch =0; for(int i=0;i<s.length();i++){ ch ^= s.charAt(i); ch ^= t.charAt(i); } ch ^= t.charAt(t.length()-1); return ch; }268 Missing Number。给一个包含n个不同数值的数组nums，数组本应该是0,1,2，…n这样的数字，但是丢了一个数字。返回丢失的数字。例如输入 nums = [0, 1, 3] 返回2。 思路：这个题目与上一提很相似。389是查找多出的字符，268是查找丢失的数字。都是从两个可比较的对象中，查找出多的或者少的部分。
public int missingNumber(int[] nums) { int xor = 0,i=0; for(i=0;i<nums.length;i++){ xor = xor^i^nums[i]; } return xor ^= i; }371 Sum of Two Integers。不用+ - 操作求两个数的和。这个解法就是比较神奇了。处理两个数相同的部分；处理两个数相异的部分。两个数相同的部分加和的时候还要向前进一，和我们手动计算和相似。
public int getSum(int a, int b) { return b == 0 ? a : getSum(a ^ b, (a & b) << 1); }参考资料
1 bit-manipulation 2 网址 3 网址 可能会有落下的网址，未列出。谢谢作者们。
