Bit Manipulation (Java) - ShuweiLeung/Thinking GitHub Wiki

该页笔记始于"2018.7.31"，结于“2018.8.3”，使用Java语言

---

1.（461:Easy）Hamming Distance

• 汉明距离是一个概念，它表示两个（相同长度）字对应位不同的数量。对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离。
• Integer.bitCount()函数返回指定 int 值的二进制补码表示形式的 1 位的数量。因为x^y是正数，正数的补码即是其原码，故可以用该函数求解。
• 更普遍的方法如下，通过"与运算"和"位移"进行bit 1的统计：

public int hammingDistance(int x, int y) {
	int res = x ^ y;
	int count = 0;
	for (int i = 0; i < 32; i++) {
		if ((res & 1) != 0) //与1求逻辑与判断个位数是否为1
			count++;
		res >>= 1; //将res数字右移一位
	}
	return count;
}

2.（476:Easy）（经典题）Number Complement

• 5的二进制是101，我们的构造的掩码为mask=111，两者异或则为010，即是所要的结果。所以首先求出输入数字的二进制位数长度，进而用掩码与其进行异或操作，具体代码如下：

public int findComplement(int num) {
	int mask = 1, temp = num;
	while(temp > 0) {
		mask = mask << 1;
		temp = temp >> 1;
	}
	//假如此时mask为10000，减1后变为1111
	return num^(mask - 1);
}

3.（693:Easy）（经典题）Binary Number with Alternating Bits

• 用1与输入的数字n进行按位与运算，所得的结果可以判断当前数字n的最低位是1还是0，同时用pre记录上一位的情况，每次逻辑与后进行比较，并将n右移一位。

4.（762:Easy）Prime Number of Set Bits in Binary Representation

• 该题使用与第3题（693）类似的思路，通过移位操作和让n与1进行按位与运算，得到当前数字二进制表示中1的个数，然后通过isPrime函数判断是否为素数即可。

5.（371:Easy）（虽然题不怎么样，但最好看一下）Sum of Two Integers

• 举个简单的例子：997+24

• 我们平时计算时是将对应位相加和进位同时计算，其实可以保留下进位，只计算对应位相加，保留进位的位置（值）。接下来，将进位向左移动一位，将上一步的结果与移位后的进位值进行对应位相加，直到没有进位结束。
• 对于二进制数的而言，对应位相加就可以使用异或（xor）操作，计算进位就可以使用与（and）操作，在下一步进行对应位相加前，对进位数使用移位操作（<<）。

6.（405:Easy）（经典题）Convert a Number to Hexadecimal

• each time we take a look at the last four digits of binary verion of the input, and maps that to a hex char shift the input to the right by 4 bits, do it again until input becomes 0. 也就是说我们每次让n与15进行按位与，获得当前数字的二进制表示的最后4位，求得其16进制表示，之后将当前数字右移4位直到0。

7.（191:Easy）Number of 1 Bits

• 该题的思路其实是和第4题（762）类似的，但区别在于该题输入的数字是无符号整型，所以右移操作要使用无符号右移">>>"。

8.（342:Easy）（经典题）Power of Four

• 一个数 num 如果是 4 的 N 次方必然也是 2 的 N 次方。所以可以先判断 num 是否是 2 的 N 次方。然后再将 2 的 N 次方中那些不是 4 的 N 次方的数去掉。
• The basic idea is from power of 2, We can use "n&(n-1) == 0" to determine if n is power of 2. For power of 4, the additional restriction is that in binary form, the only "1" should always located at the odd position. For example, 4^0 = 1, 4^1 = 100, 4^2 = 10000. So we can use "num & 0x55555555==num" to check if "1" is located at the odd position.
• 将2的幂次方写成二进制形式后，很容易就会发现有一个特点：二进制中只有一个1，并且1后面跟了n个0。如果将这个数减去1后会发现，仅有的那个1会变为0，而原来的那n个0会变为1；因此将原来的数与减去1后的数字进行与运算后会发现为零。所以"n&(n-1) == 0"可以判断n是否为2的幂次。
• 0x55555555代表32位数，包含了所有可能的4的幂情况

9.（190:Easy）（经典题）Reverse Bits

• 该题也和第4题（762）类似，用按位与操作获得当前数字n的最低位，并将其加到reversedNum变量上，并将reversedNum左移一位，同时n无符号右移一位。
• 注意：对于最后一次右移（第32次，因为unsigned int是32位），无需左移reversedNum，因为已经没必要再往上加数字了。

10.（137:Medium）（非常经典题）Single Number II

• 该题最简单的方法是用一个HashMap来统计每一个数出现的次数，最后找出只出现一次的数返回即可。
• 对于线性时间解决该问题，必须使用bit manipulation来求解。思路是：因为int可以表示成32位数，所以按位进行数组中数字的处理。我们统计每个数字相同位的值，如果是1的话加到sum变量上。一旦某个数出现了3次，那么sum%3一定会消去该数字对sum值的贡献，从而遍历完整个数组，sum保存的只是出现了一次的数字对当前位的贡献值，从而通过sum的位移操作恢复答案数字的当前位。假如题目中除了一个数字出现了1次，其他数字都出现了5次，只需要改为sum%5即可。具体的代码参考如下：

public int singleNumber(int[] nums) {
   int ans = 0;
   for(int i = 0; i < 32; i++) {  //int是32位数
       int sum = 0;   //对每一位都求一次和
       for(int j = 0; j < nums.length; j++) {
           if(((nums[j] >> i) & 1) == 1) {   //对每一个数的第i位求和，与1进行按位与就是该位的值，如果等于1的话就加到sum上
               sum++;
               sum %= 3;  //每次都对3取余，及时消去出现3次的数的对应位的值
           }
       }
       if(sum != 0) {  //sum！=0，说明此时的sum代表只出现一次的数的第i位值
           ans |= sum << i; //按位或运算看成加法
       }
   }
   return ans;
}

• 参考链接：Single Numer I 的解法

11.（260:Medium）（非常经典题）Single Number III

• 该题首先要有Single Number I的基础，Single Number I的思路请参看上题的参考链接。该题首先用异或操作获得只出现一次的两个数的异或值，之后用该异或值得到区分两数的信息，然后再来一便轮流异或操作获得两数，具体思路请参看代码及参考链接。
• 参考链接：Single Number III解法清晰讲解博客

    public int[] singleNumber(int[] nums) {
	//下面的操作原理请参看Single Number I，最后所有数字异或的结果是只出现一次的数字的异或值
        int AXORB = 0;
        for (int num : nums) {
            AXORB ^= num;
        }
		
        // pick one bit as flag
        int bitFlag = (AXORB & (~ (AXORB - 1)));   //用来求最右边第一个A和B不相同的一位，例如A=11000 B = 01010，AXORB=10010，~(AXORB-1)=01110,与AXORB进行与操作得00010
        int[] res = new int[2];
        for (int num : nums) {
            if ((num & bitFlag) == 0) {
                res[0] ^= num;   //出现两次的数异或为0，不贡献值
            } else {
                res[1] ^= num;
            }
        }
        return res;
    }

<12>???（421:Medium）（不会做，学Trie的数据结构）Maximum XOR of Two Numbers in an Array

要在线性时间解决该问题，不会做，需要用Trie的数据结构

13.（477:Medium）（非常经典题）Total Hamming Distance

• 按照两个数的汉明距离的求法，利用位操作符对每两个数先求异或，然后统计结果中1的个数，时间复杂度为O(n^2)，超时。
• Discuss中参考思路是：考虑所有数字的同一个bit位，统计在这个bit位上出现的1的次数count，那么这个bit位在总的汉明距离中就贡献了count(n-count)，n是数组中元素的个数*。因为当前位是1的元素和当前位为0的元素共有count*(n - count)个组合。具体可以参见代码及注释。

14.（318:Medium）（非常经典题）Maximum Product of Word Lengths

• int值有32位，一共有26个字母，因此我们用一个int数的后26位表示一个word的字母种类，用mask数组保存，mask[i]代表第i个数中字母种类的情况。那么当两个word对应的mask相与为0时，代表两个单词无重复内容，求其长度的乘积即可。具体代码如下：

public int maxProduct(String[] words) {
     int len=words.length;
     if (len<=1) return 0;
     int[] mask=new int[len];  //mask[i]记录每一个word中字符的种类
     //abcd可以length=4
     //words[i].charAt(0) 0左移0位
     for (int i = 0; i < len; i++) {
         for (int j = 0; j <words[i].length() ; j++) {
             mask[i] |= 1<<(words[i].charAt(j)-'a');   
         }
     }
     int max= 0;
     for (int i = 0; i < len; i++) {
         for (int j = i+1; j <len ; j++) {
             if((mask[i] & mask[j]) == 0){ //如果两个word不想同，才求长度的乘积
                 max=Math.max(max,words[i].length()*words[j].length());
             }
         }
     }
     return max;
}

15.（201:Medium）（非常经典题）Bitwise AND of Numbers Range

• 该题当然能暴力求解，但非常耗时。
• 巧妙的办法是：考虑数据的二进制形式。

对于整数m到n，在数值连续变化的过程中，它们的某些高位比特是相同的，而只有低位的比特连续变化。

例如：整数：33，34，35，36

它们的二进制形式是（为了简单，我们假设每个数值有8个bits）：

33 : 00100001
34 : 00100010
35 : 00100011
36 : 00100100

不难看出，它们都具有00100xxx的形式，共同的高位比特是：00100。如果进行按位与运算(&)的话，这些高位是保持不变的。

再看低位（低3位比特）。与运算之后的结果是000。

由上面的分析，可以得到：

为了得到它们与运算的结果，我们只需要找出区间[m, n]范围内所有数值的共同高比特位即可。

又因为m和n是这些数中相差最大的，所以它俩拥有的共同高位比特也是最少的。所以计算中只需要用m和n即可。

• 参考链接：中文博客思路详解