首先由一道题目引入
面试题 17.04. 消失的数字
题目描述：
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
示例 1：输入：[3,0,1] 输出：2
自己第一次提交代码：建立哈希表，需O(n)辅助空间
class Solution {
public int missingNumber(int[] nums) {
int i, n = nums.length;
int[] hash = new int[n+1];
for(i = 0; i<n; i++){
hash[nums[i]] = 1;
}
for(i = 0; i<=n; i++){
if(hash[i]==0)
return i;
}
return 0;
}
}参考题解有两种更灵活巧妙的思路：
解法1：按照题意，将预期的所有整数相加，减去给定数组的所有整数的和，得到的就是消失的数字。
class Solution {
public int missingNumber(int[] nums) {
int sum = (nums.length + 1) * nums.length / 2;
int arraySum = 0;
for (int i = 0; i < nums.length; i++) arraySum += nums[i];
return sum - arraySum;
}
}解法2：根据异或运算的特性去解题。res = res ^ x ^ x。
利用异或的特性，res = res ^ x ^ x。值res对同一个值异或两次，那么结果等于它本身，所以我们对res从0-nums.length进行异或，同时对nums数组中的值进行异或，出现重复的会消失，所以最后res的值是只出现一次的数字，也就是nums数组中缺失的那个数字。
class Solution {
public int missingNumber(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; ++i) {
res ^= i;
res ^= nums[i];
}
res ^= nums.length;
return res;
}
}一、异或^运算的特性
异或（“ ^ ”）对运算符两侧数的每一个二进制位，同值取0，异值取1。
- x^0 = x 且 x^x = 0 【消去偶数次出现的数】
- 交换律：x^y = y^x
- 结合律：(x^y)^z = x^(y^z)
- 自反性：x^y^y = x 【得到唯一单数次出现的数】
自反性的应用
题型一：交换两个变量的值
如果使用异或，就可以不使用中间变量：设有A,B两个变量，存储的值分别为a，b，则以下三行表达式将互换他们的值【表达式（值）】 ：
A = A ^ B (a ^ b)
B = B ^ A (b ^ a ^ b = a)
A = A ^ B (a ^ b ^ a = b)
类似地，该运算还可以应用在加密，数据传输，校验等等许多领域。
题型二：唯一出现单数次的数
（思路：性质 自反性部分红色字标出）
题型三：巧用位运算：解题小Tips
判断一个数的二进制表示全为1
boolean res = (temp & (temp+1))==0
不用 + 加号计算 a+b
int res = (a^b) + ((a&b)<<1)
题型四：（进阶）A集合里拿掉数x、y得到B集合，求x和y
令XOR(X)表示将X集合内所有的数做异或
首先按上一个的办法可以推导出xor(A)^xor(B) = xor(B)^xor(B)^x^y = 0^x^y = x^y
x^y的二进制结果，第n位为1，说明x和y的第n位不相同
根据第n位是否为0把A里所有的数分成A1和A0两个数组（A1里的数的二进制第n位都是1，A0都是0），A1和A0应该各包含了a或者b（这样第n位才能异或出1），同理可以把B分成B1和B0两个数组，可以得到第一个数 x = A1^B1，第二个数可以y = A0^B0，当然也可以用x^y^x求得。
另外如果x^y为0，即x == y，令SUM(X)为X集合内所有数求和，(SUM(A) - SUM(B)) / 2 = x。
没有^操作时候实现异或,只用&与 |或 ~非
转换方法有很多，如 x ^ y == (~x & y) | (x & ~y)
二、移位运算的特性
移位运算时间效率比乘除法高很多
Java中整型数据的存储
在应用移位操作来解决问题之前，我们先明确一下java整形数据是如何以二进制形式存储，从而更好地理解移位的定义。
1. 符号位
首先，没有用unsigned定义的整型默认为有符号整型，正数符号位为0，负数为1，通过测试代码取符号位：
//取符号位（与int存储为32/64位无关）
class dailyPractice {
public static void main(String[] args){
int a = -1, b = 1, c;
c = (a>>(Integer.SIZE - 1))&1;
System.out.println(c); //输出1
c = (b>>(Integer.SIZE - 1))&1;
System.out.println(c); //输出0
}
}2. 补码存储
计算机中存储整型数用补码进行存储，位运算也是用补码直接进行位运算
反码表示法：正数的反码与其原码相同；负数的反码是（除符号位外）对其原码逐位取反。
补码表示法：正数的补码与其原码相同；负数的补码是在其反码的末位加1。
以负数-5为例：
先将-5的绝对值转换成二进制，即为0000 0101；然后求该二进制的反码，即为 1111 1010；最后将反码加1，即为：1111 1011
复习了这些最最基本的东西再来看移位的定义就对"补符号位"有更直观的感受了。
Java中没有“无符号整形”这种数据类型
移位规则
左移（<<） : m<<n表示 把m左移n位，最左边的n位会被丢弃，同时最右边补上n个0；
右移（>>）：m>>n表示 把m右移n位 最右边的n为会被丢弃，如果数值原来是个正数，用0补上最左边的n位，如果是一个负数，则最左边补上n个1；
int a = 8, b = -8;
System.out.println(a<<1); //16
System.out.println(b<<1); //-16
System.out.println(a>>1); //4
System.out.println(b>>1); //-4由实际代码输出可以看出java中的负数右移并没有带着符号位右移并且在前面部符号位，实际上是做的算数右移。JAVA 和 Python中：算术右移 A >> B , 逻辑右移 A >>> B。
算术右移：将A的二进制表示的每一位向右移B位，右边超出的位截掉，左边不足的位补符号位的数。
逻辑右移：将A的二进制表示的每一位向右移B位，右边超出的位截掉，左边不足的位补0。
测试代码：
//算术右移
class dailyPractice {
public static void main(String[] args){
int i, cnt=0, a = -5, b = a>>1, s = 4*8;
int[] store = new int[s];
System.out.println("右移前：a="+a);
while(cnt++<s){
store[s-cnt] = a&1;
a = a>>1;
}
for(i = 0; i<s; i++)
System.out.print(store[i]);
cnt = 0;
System.out.println("\n右移后: a="+b);
while(cnt++<s){
store[s-cnt] = b&1;
b = b>>1;
}
for(i = 0; i<s; i++)
System.out.print(store[i]);
}
}输出：
(a=-5) 右移前：a=-5 11111111111111111111111111111011 右移后: a=-3 11111111111111111111111111111101 (a=5) 右移前：a=5 00000000000000000000000000000101 右移后: a=2 00000000000000000000000000000010
题型一：二进制中1的个数
题目描述：实现一个函数，输入一个整数，输出这个数字二进制中表示1的个数。如，把9表示成二进制是1001，有2个1。因此输入9，函数输出为2。
思路一： 利用循环，每次将数字n与1做位与（&）运算，检验最优以为是不是1，然后将数字n右移一位，循环终止条件为n为0；
【这种思想的问题在于，如果n为负数，在右移操作时，最左边将会用1填充，则会陷入死循环中。】
思路二（避免死循环）：设置一个mask=1，把数字n与mask进行位与运算，判断n的mask位是不是1，,然后mask左移一位，再和n位与，判断n的次低位是不是1；
【这样的想法，循环的次数是整数二进制的位数；循环的次数有点儿多啊】
改进一下，n中有几个1就循环几次的算法：
一个规律，一个整数减去1，再与原整数做与运算，即：n &(n-1) 会将该整数的从右边数第一个1变成0 ，这样该整数中有几个1就循环几次，直至把该整数中的1都变成0；
题型二：一条语句判断一个整数是不是2的整数次方
方法：利用 n&(n-1)
利用上一个题中最后的思路，因为分析可知，如果一个整数是2的整数次方，则其二进制表示中，有且仅有一个1，所以，只要利用 n&(n-1) 判断其值是否为0即可；
进一步，给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。
class Solution {
//如果只有一位是1且每次右移两位能够遇到则返回true
public boolean isPowerOfFour(int num) {
if(num==0 || n&(n-1)==0)
while(num!=0){
if(num%2==1)
return true;
num = num >> 2;
}
return false;
}
}题型三：判断一个数二进制形式存储中某一位的值
方法：移位后&1
//取num的二进制存储形式（由右向左数）第bit位的值
public int valueAtBit(int num, int bit) {
return (num >> (bit -1)) & 1;
}以(128,8)为例分析：
128->1000 0000；要想将第八位上的数字取出，可以将它移到第一位上，也即是向右移动7位变成0000 0001，怎样将第一位上的1拿出来呢，可以利用与操作，让0000 0001，与1（0000 0001）与，除了第一位上的数是它本身，其余位全部变成了0，这样就将第一位取了出来。
题型四：一个数字改变几位得到另一个数字
方法：利用异或的概念
题目描述：输入两个整数m和n，计算需要改变m的二进制中的多少位能得到n。比如10的二进制表示为1010，13的二进制位1101，需要改变3位。
解决该问题可以分为两步，首先m和n进行异或，然后统计异或的结果中有多少个1，方法见题型二。
接着由一道题进阶
LeetCode 137. 只出现一次的数字 II
题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。(你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？)
示例 1: 输入: [2,2,3,2] 输出: 3
如何用位运算来做呢？
【请不要偷懒直接看下面的讲解，停在这里自己思考完成一次思维训练呀】
通用解法
统计所有数字中每个位中1出现的总数，那么对于某个位，1出现的次数一定是3的倍数+1或0，那么对这个数%3得到的结果就是目的数字在该位上的值。思想简单、通用 (很容易推广到“其余数字出现n次”)，但时间复杂度比较高，比位运算多一层循环。
class Solution {
public int singleNumber(int[] nums) {
int ret = 0;
for (int i = 0; i < 32; i++) {
int mask = 1 << i;
int cnt = 0;
for (int j = 0; j < nums.length; j++) {
if ((nums[j] & mask) != 0) {
cnt++;
}
}
if (cnt % 3 != 0) {
ret |= mask;
}
}
return ret;
}
}位运算解法
本题的解法思路与136题类似，在136题中我们使用异或运算使得相同的两个数运算的结果为0，在本题中，我们需要思考的问题是，我们是否能够定义一种运算（代替异或），使得三个数运算的结果为 0 呢？
答案是肯定的，在这里我们使用一种数字电路设计的思路来设计。
重新回到本题，我们的目标是使得三个数的运算结果为 0。你会发现三进制不计进位的加法恰好符合我们的要求：三个1相加结果为0。因此我们需要设计一个三进制的计数器。
首先，三进制需要2个bit来表示（00，01，10，11），因此我们用 one 和 two 这两个变量分别存放我们的 2 个 bit。因为我们要求的是三进制，因此我们只需要 00, 01, 10 这三个状态，首先我们列出状态转移方程：
接下来，我们需要通过状态转移表来得出newOne 和 one，two，num以及newTwo和one，two，num直接的逻辑关系。为了简化这种逻辑推断的复杂度，我们使用卡诺图来做，首先画出newOne的卡诺图：
- 区域必须是长方形（正方形）；
卡诺图上下左右是联通的；
区域内只能包含1或X；
区域的大小必须是2的幂（2，4，8……）；
每个区域尽可能地大；
画完后不能有1在区域外；
因此我们得出的结果是：
这样我们就创造出了我们新的运算，代码就很简单啦：
代码
class Solution {
public int singleNumber(int[] nums) {
int one = 0, two = 0, temp = 0;
for (int num : nums) {
temp = (two & num) | (one & ~num);
two = (~one & ~two & num) | (two & ~num);
one = temp;
}
return two;
// 这里return two的原因是第二个状态为 01，one 为 0，two 为 1
}
}位运算时间复杂度优化Tips:
1.以优于 &preview=true)
为目标
方法一：按位统计
明确识别出用位运算来做的题目，如果写出来复杂度为，就还是不够好，很可能会超时。如果思路要用双层循环O(n^2)，可以考虑用按位统计的思路将复杂度降到32*n。
Leetcode.477汉明距离总和
题目描述：两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。计算一个数组中，任意两个数之间汉明距离的总和。
class Solution {
public int totalHammingDistance(int[] nums) {
int i, j, n = nums.length, sum = 0;
for(i = 0; i<n; i++){
for(j = 0; j<n; j++){
sum += Integer.bitCount(nums[i]^nums[j]);
}
}
return sum>>1;
}
}代码超时了，实际上是的复杂度。以为自己用上了位运算就是面试官想要的代码了，就还太飘（还是要习惯于勤于思考）。
class Solution {
public int totalHammingDistance(int[] nums) {
int i, n = nums.length, res = 0;
int[] cnt = new int[32];
for(int num: nums){
for(i = 0; i<32; i++){
cnt[i] += num & 1;
num = num>>1;
}
}
for(i = 0; i<32; i++){
res += cnt[i]*(n-cnt[i]);
}
return res;
}
}《 java 自带的计算二进制“1”的位数等一些函数是如何实现的？是否是效率最高的方式》
京公网安备 11010502036488号