leetcode实战—位运算（两数相除、只出现一次的数字、重复的

作者: 佛西先森 | 来源:发表于2020-03-20 20:49 被阅读0次

前言

对0和1的操作是计算机最底层的操作，所有的程序不管用什么语言写的，都要转化成机器能够读懂的语言也就是二进制进行基本的运算，而这些基本的运算就是我们今天要讲到的位运算。因为硬件的支持，计算机在进行二进制计算的时候要比普通的十进制计算快的多，把普通的运算用位运算的方法实现能够极大提高程序性能，是一个重要的技能。

简介

在计算机中有超过七种位运算操作，在这里就以Java为例来讲解Java中需要用到的七种位运算符。

符号	描述	规则	举例
&	按位与	左右两侧同时为1得到1，否则为0	1&1=1 1&0=0
\|	按位或	左右两侧只要一个是1就返回1，都是0才返回0	1\|0=1 0\|0=0
^	按位异或	左右两侧相同时为0，不同为1	1^1=0<br>00=0 1^0=1
~	按位取反	1变成0，0变成1	_1=0<br>0=1
<<	有符号左移	保持最高位的符号，其他的位向左移动，右侧用0补齐	1<<2=4
>>	有符号右移	保持最高位符号，其他位向右移动，除最高位其他用0补齐	5>>1=2 -10>>1=-5
>>>	无符号右移	所有位都向左移动，高位用0补齐	5>>>1=2 -10>>>1=2147483643

既然说到了位运算就不得不提一下在Java中int类型数字的表示，Java的int一共是32位，其中第32位符号标志位，如果是0就代表是正数，1代表是负数，比如1的表示方法是0000 0000 0000 0000 0000 0000 0000 0001，最大只能是前31位都置1的结果，也就是 $2^{31}-1$ ；对于负数的表示需要注意，并不是直接把对应的正数最高位0变成1，而是全部位取反然后加一，这样做的目的是为了让两个二进制数字直接相加的和为0，比如-1的表示方法是1111 1111 1111 1111 1111 1111 1111 1111，这样两个数字二进制相加得到的最终结果是0（最高位溢出舍弃掉）。负数的最小值是 $2^{31}$ ，绝对值比正数最大值大一位，因为这个负数比较特殊，二进制表示为1000 0000 0000 0000 0000 0000 0000 0000，在取反加一之后还是它本身。

这里顺带介绍一下位操作的小技巧，其中的原理可以自己揣摩

序号	公式	解释（`n`从`0`开始）
1	num \|= 1<<n	将`num`第`n`位设置为`1`
2	num &= ~(1<<n)	将`num`第`n`位设置为`0`
3	num ^= 1<<n	将`num`第`n`位取反
4	num & (1<<n) == (1<<n)	检查`num`第`n`位是否为`1`
5	num = num & (num-1)	将`num`最低位的`1`置`0`
6	num & -num	获得`num`最低位的`1`
7	num &= ~((1<<n+1)-1)	将`num`最`n`位右侧置`0`
8	num &= (1<<n)-1	将`num`第`n`位左侧置`0`

更多位操作相关技巧可以看这里这里。

这里捎带着说一下浮点类型float在Java中的表示，如果已经比较清楚的同学可以直接跳过这个部分。浮点数总共4个字节，表示可以用下面的公式：

$(-1)^s \times m \times 2^{e-127}$

其中

s，第31位，如果是1代表是负数，0代表正数
e，第30~23位，是指数位，表示一个无符号的整数，最大是255
m，第22~0位，尾数，包含了隐藏的1，表示小数位，需要去掉后面的无效的0

比如在浮点数0.15625在二进制中的表示方法是0011 1110 0010 0000 0000 0000 0000 0000（使用Java代码Integer.toBinaryString(Float.floatToIntBits(0.15625F))可以得到浮点数的二进制表示，但是省去了最高位的0），其中

第31位0，表示正数
第30~23位，011 1110 0指数位，十进制是124，减去127之后得到-3
第22~0位，010 0000 0000 0000 0000 0000尾数数，舍去小数后面的0之后得到01，加上默认1后得到1.01（二进制表示的小数）
综上根据公式得到0.15625的二进制公式为 $(-1)^0\times(1.01)\times2^{-3}=0.00101$ ，然后把二进制转成十进制就变成了 $2^{-3}+2^{-5}=0.125+0.03125=0.15625$

double类型和float的计算方法一样，只不过double的指数位有11位，尾数位52位，计算指数的时候需要减去1023。相比于float，double的精度要高很多，如果不在意空间消耗的情况下，最好用double。

leetcode相关题目

现在基本的计算机的操作我们知道了，数字的二进制表示我们也清楚了，那么如何通过二进制的位运算来完成十进制数字的计算呢？下面来一一揭晓。

371 两整数之和

Leetcode第371题两整数之和

不使用运算符+和-，计算两整数a、b之和。

示例1：

输入: a = 1, b = 2
输出: 3

示例2：

输入: a = -2, b = 3
输出: 1

这道题在leetcode的美国网站上面有1900多个dislike，看来大家对这个题目意见很大，不过就趁这个机会回顾一下计算机是怎样进行加法操作的。

回顾一下我们小学就开始学习的十进制的加法，比如15+7，最低位5+7得到12，对10取模得到2，进位为1，再高位相加1+0再加上进位1就得到高位结果2,组合起来就是22。这里面涉及到了两个数字，一个是相加得到的低位，也就是5+7得到的结果2，第二个是进位1。在二进制的计算中就是要通过位操作来得到结果的低位和进位，对于不同的情况，用表格来表示一下，两个数字分别为a和b

a	b	低位	进位
0	0	0	0
1	0	1	0
0	1	1	0
1	1	0	1

从上面的表格就可以发现，低位 = a^b，进位 = a & b。这样的计算可能要持续多次，回想一下在十进制的计算中，如果进位一直大于0，就得往后面进行计算，在这里也是一样，只要进位不是0，我们就得一直重复计算低位和进位的操作（需要在下一次计算之前要把进位向左移动一位，这样进位才能和更高位进行运算）。这个时候的a和b就是刚才计算的低位和进位，用简单的加法迭代的代码表示：

public int getSum(int a, int b) {
    if (a==0) return b;
    if (b==0) return a;
    int lower;
    int carrier;
    while (true) {
        lower = a^b;    // 计算低位
        carrier = a&b;  // 计算进位
        if (carrier==0) break;
        a = lower;
        b = carrier<<1;
    }
    return lower;
}

29 两数相除

这是leetcode第19题两数相除

给定两个整数，被除数dividend和除数divisor。将两数相除，要求不使用乘法、除法和mod运算符。

返回被除数dividend除以除数divisor得到的商。

示例1：

输入: dividend = 10, divisor = 3
输出: 3

示例2：

输入: dividend = 7, divisor = -3
输出: -2

说明：

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 $[−2^{31}, 2^{31} − 1]$ 。本题中，如果除法结果溢出，则返回 $2^{31} − 1$ 。

这道题其实可以很容易联想到我们经常用到的十进制的除法，这里有一个例子来说明如何把十进制除法的思想套用在二进制上面。

binary division

图片是用33除以6，对应二进制100001除以110，有三步：

将被除数从110开始向左移位右侧补0，直到找到最大的比100001小的数字11000（图中右侧的0已经被省略掉了），这个时候向左移动了两位也就是乘以100（二进制），余数是1000
再将110向左移动到最大的比1000小数字，这个时候就是本身，相当于乘以1（向左移动了0位），余数是11
因为余数已经比被除数110要小了，这个时候可以直接停止运算，将上面两个步骤计算得到的乘数（100和1）加起来就是我们最后的结果了（101）。

这里我们就用java代码来实现一下这个逻辑：

public int divide(int dividendInt, int divisorInt) {
    int shiftedDivisor;                   // 移位后的除数
    int quotient = 0;                     // 记录除法得到的商
    int remainder = dividendInt;

    while (remainder>=divisorInt) {
        int tempQuotient = 1;             // 临时的商
        dividendInt = remainder;          // 处理上一轮的余数
        shiftedDivisor = divisorInt;      // 重置被除数
        while (dividendInt>=shiftedDivisor) {
            shiftedDivisor <<=1;
            tempQuotient <<= 1;
        }
        quotient += tempQuotient >> 1;    // 累加计算得到的商
        remainder = dividendInt - (shiftedDivisor >> 1); // 位移优先级比减号低，要用括号
    }
    return quotient;
}

通过循环的方法得到了我们要的除法的实现逻辑，但是这个方法只是对除数和被除数都是正数才起作用，比如除数是-100被除数是10或者-10的时候，返回的结果是0！对于-100除以-10这个例子，在比较余数和移位的除数的大小的时候，如果都是正数，余数比除数小的时候停止循环是正常的，但是在都是负数的时候，这样做就有问题了，余数比除数大，商才是0，所以上面两个循环的终止条件的不等号方向换一下就可以了。

public int divide(int dividendInt, int divisorInt) {
    int shiftedDivisor;
    int quotient = 0;
    int remainder = dividendInt;

    while (remainder<=divisorInt) {           // 注意 变成了小于等于
        int tempQuotient = 1;
        dividendInt = remainder;
        shiftedDivisor = divisorInt;
        while (dividendInt<=shiftedDivisor) {  // 注意 变成了小于等于
            shiftedDivisor <<=1;
            tempQuotient <<= 1;
        }
        quotient += tempQuotient >> 1;
        remainder = dividendInt - (shiftedDivisor >> 1);
    }
    return quotient;
}

现在我们都是正数和都是负数的情况都有了，一个正数一个负数咋办呢？那就把符号变一下，变成一样的，最后在返回结果的时候变回来。这里题目善意的提醒了一下要考虑边界问题，在考虑转换符号的时候需要考虑到-2147483648这个值的特殊性，也就是负数变正数要小心，但是正数变成负数可以随意，那就不如直接负数运算得了（参考这篇文章）。在累加每一次除法得到的商的时候，也是使用负数-1的移位来避免溢出问题（比如-2147483648除以1带来的溢出问题）。

在对除数进行移位的时候，还需要注意一下移位之后除数不能溢出，能够使用的最好方法就是在移位之前判断一下除数是否是小于最小数字的一半（如果是用正数移位的话，就应该是判断是否是大于最大数字的一半），如果小于，下一次移位一定就会溢出，这个时候就只能直接终止循环。

在判断结果的符号的时候用一下位运算的小技巧，在上面讲到异或操作的时候，如果是相同的就返回0，否则是1，所以对两个数字最高位进行异或操作，如果是0就代表结果是正号，反之就是负号。除此之外还有一个极端情况，当被除数取最小值-2147483648并且除数取-1的时候，得到的结果是2147483648会溢出，因为只有这样的一个特例，可以直接排除，对于剩下的其他的数字不管怎样都不会溢出，整理之后的代码如下：

public int divide(int dividendInt, int divisorInt) {
    if (dividendInt == Integer.MIN_VALUE && divisorInt == -1) {
        return Integer.MAX_VALUE;         // 对于极端情况，直接排除，返回int最大值
    }
    boolean negSig =
            ((dividendInt ^ divisorInt) & Integer.MIN_VALUE) == Integer.MIN_VALUE;  // 判断结果是否是负数

    dividendInt = dividendInt > 0 ? -dividendInt : dividendInt;                     // 被除数取负值
    divisorInt = divisorInt > 0 ? -divisorInt : divisorInt;                         // 除数取负值

    int shiftedDivisor;                   // 移位后的除数
    int quotient = 0;                     // 记录除法得到的商
    int remainder = dividendInt;
    int minShiftDivisor = Integer.MIN_VALUE >> 1; // 防止溢出，大于这个值之后不能再向左移位了

    while (remainder<=divisorInt) {
        int tempQuotient = -1;             // 临时的商，全部用负数处理
        dividendInt = remainder;           // 处理上一轮的余数
        shiftedDivisor = divisorInt;       // 重置被除数
        while (dividendInt<=(shiftedDivisor<<1)          // 比被除数小才进行接下来的计算
                && shiftedDivisor >= minShiftDivisor) {  // 判断是否移位后会溢出
            shiftedDivisor <<=1;
            tempQuotient <<= 1;
        }
        quotient += tempQuotient;                        // 累加计算得到的商
        remainder = dividendInt - shiftedDivisor;        // 得到余数，下一轮作为新的被除数
    }

    return negSig?quotient:-quotient;     // 如果是负数就直接返回结果，如果不是就变换成正数
}

191. 位1的个数

leetcode第191题位1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为1的个数（也被称为汉明重量）。

示例1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串00000000000000000000000000001011中，共有三位为'1'。

示例2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串00000000000000000000000010000000中，共有一位为 '1'。

这道题最简单暴力的做法就是直接移位，在Java里面直接用无符号的右移，每次判断最低位是不是1，把判断为1的所有的次数记录起来就可以了。

public int hammingWeight(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        count += n&1;  // 累加1
        n>>>=1;        // 循环右移1位
    }
    return count;
}

但是这道题有一个更加有意思的解法，首先对于一个二进制数字比如10100，在减一操作之后得到10011，比较这两个数字，发现原数字最低位的1的右边的数字没有变，而右边的0都变成了1，而这个1变成了0，如果对原来的数字和减一的数字进行按位与，就会把最低位的1置零。

所以就有了一个神奇的想法，如果我们想把数字a最低位的1变成0而不改变其他位，直接通过a&(a-1)就可以得到了，而把所有的1都变成了0的次数不就是位1的个数了吗？

比如对于数字101，在经过a&(a-1) = 101&100 = 100，再操作一次就是100&011 = 0，一共两次操作，最后的结果就变成了0。

简单代码如下：

public int hammingWeight(int n) {
    int count = 0;    // 统计置0的次数
    while (n!=0) {
        count ++;
        n = n&(n-1);  // 最低位的1置0
    }
    return count;
}

看起来上面两个算法都可以达到我们想要的目的，但是不知道效率怎么样，那就来测试比较一下（添加的java的内置计算1个数的方法）

private void test() {
    int t = 10000000;                        // 比较一千万次
    long s = System.currentTimeMillis();
    for (int i = 0; i < t; i++) {
        hammingWeight1(-3);
    }
    System.out.println("Java builtin:\t" + (System.currentTimeMillis()-s));
    s = System.currentTimeMillis();
    for (int i = 0; i < t; i++) {
        hammingWeight2(-3);
    }
    System.out.println("最低位1置0:   \t" + (System.currentTimeMillis()-s));
    s = System.currentTimeMillis();
    for (int i = 0; i < t; i++) {
        hammingWeight3(-3);
    }
    System.out.println("向右移位比较:\t" + (System.currentTimeMillis()-s));
}

// java内置方法
public int hammingWeight1(int n) {
    return Integer.bitCount(n);
}

// 最低位1置0
public int hammingWeight2(int n) {
    int count = 0;
    while (n!=0) {
        count ++;
        n = n&(n-1);
    }
    return count;
}

// 向右移位比较
public int hammingWeight3(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        count += n&1;  // 累加1
        n>>>=1;        // 循环右移1位
    }
    return count;
}

输出的结果如下：

Java builtin:   10
最低位1置0:     150
向右移位比较:    10

虽然上面只是一次测试的结果（每次运行测试的时候结果都不一样），但是可以看出最低位置0这个方法效率要比普通的移位操作或者内置的方法慢一个数量级，猜测原因应该是n=n&(n-1)这个操作耗时比较高（n=n&(n-1)其实是两步，第一步int a = n-1，第二步n=n&a），而n&1或者n>>>=1这两个操作都要快很多。

回到测试，多测几次发现java内置的方法有的时候要比向右移位快很多，这就有意思了，得看看它到底是怎么实现的：

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

看完之后一句卧槽涌上心头，这写的是什么玩意儿？！这是什么神仙算法！那就来仔细看看这个算法，对每一步进行分解，假设我们的输入是-1

public static int bitCount(int i) {                  // i = 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11  -1的二进制
    // HD, Figure 5-2                                //     01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01  
    i = i - ((i >>> 1) & 0x55555555);                // i = 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10  (1)每2位的计算
                                                     //     00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11  
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); // i = 0100 0100 0100 0100 0100 0100 0100 0100          (2)每4位求和
                                                     //     0000 1111 0000 1111 0000 1111 0000 1111
    i = (i + (i >>> 4)) & 0x0f0f0f0f;                // i = 00001000 00001000 00001000 00001000          (3)每8位求和

    i = i + (i >>> 8);                               // i = 0000100000010000 0001000000010000            (4)每16位求和

    i = i + (i >>> 16);                              // i = 00001000000100000001100000100000             (5)每32位求和

    return i & 0x3f;                                 // i = 00000000000000000000000000 100000            (6)取最低的6位
}

这个过程一共有6步，主要思想就是分治法，计算每2、4、8、16、32位中1的个数：

第一步也是最重要的一步，统计每2位里面的1的个数，比如二进制11有两个1应该变成统计结果10（11-((11>>>1)&01) = 10），10或者01应该变成01（10-((10>>>1)&01) = 01，01-((01>>>1)&01) = 01）
统计每4位里面的1的个数，也就是把上面计算得到的两位1的个数和相加，比如01 00，通过移位并且和掩码0011按位与，变成0000和0001然后求和得到0001
统计每8位二进制里面1的个数，这一步跟上面又不一样了，不是先用掩码再相加，而是先相加再用掩码，主要不同地方是在上一步两个二位的二进制数字相加可能会溢出，使用掩码之后就会得到错误的结果，比如10 10，相加得到01 00然后用00 11按位与得到00 00不是我们想要的结果。当计算8位的个数的时候就不会溢出，因为4位里面1的个数最多是4个，也就是0100，两个相加最大是1000，不会进位到第二个4位，使用掩码能够得到正确的结果，并且可以清除多余的1
统计每16位二进制里面1的个数，这个时候直接移位相加并没有用掩码，原因很简单，在上一步的每8位里面的的结果的是保存在最后4位里面，并且一定是准确的，直接相加肯定不会溢出8位，结果也一定保存在最右边的8位里面，至于16位里面的左边的8位是什么值我们根本就不关心，所以没有必要用掩码，也不会影响后面的计算
这一步得到32位的和，直接移位相加，因为左右16位的1的个数一定保存在他们各自的右侧8位，相加的结果也不会溢出，一定还在最右的8位里面，左边的24位是什么也没有影响
结果一定在最后的6位里面，因为一共最多只有32个1，只需要6位来保存这个值。

这样就通过一个精细的二进制的运算利用分治法得到了最后1的个数，不得不感叹这样的做法实在是太妙了！

Java中还有很多精妙的整型数字的位操作方法比如下面的几种，虽然很想介绍一下，不过因为篇幅原因就跳过，因为后面还有更加重要的内容

highestOneBit
lowestOneBit
numberOfLeadingZeros
numberOfTrailingZeros
reverse
rotateLeft
rotateRight

268 缺失数字

leetcode第268题缺失数字

给定一个包含0, 1, 2, ..., n中n个数的序列，找出0 .. n中没有出现在序列中的那个数。

示例1：

输入: [3,0,1]
输出: 2

这道题可以用哈希表或者求和的方法，都是不错的方法，不过既然这篇文章是关于位运算的，就用经典的位运算吧。

对于数字的位运算，按位异或有一个很重要的性质，对于数字a和b有：

a^a=0

a^0=a

a^b^a=b

以此类推可以发现如果对于一个数组里面的每一个元素都进行按位异或，里面的出现频率是偶数的元素都会变成0，如果数组里面每个元素的出现频率都是偶数次，那么整个数组的按位异或的结果就是0，如果只有一个元素出现了奇数次，按位异或的结果就是这个元素。

回到这道题，数组中所有的数字出现的次数是1，没有出现的数字次数是0，明显不能直接按位异或，那我们就再这个数组后面添加一个0..n的数组，包含所有的元素，这样两个数组合起来原来出现的数字的出现次数是2，而原来没有出现的数字的出现次数是1，就可以用按位异或了。

不过这里并不需要显性的添加数组，而是在循环内部再进行异或操作，代码如下：

public int missingNumber(int[] nums) {
    int xor = 0;
    for (int i = 0; i < nums.length; i++) {
        xor ^= i^nums[i];           // 循环内部尽量按位异或虚拟的新增数组
    }
    return xor^nums.length;         // 补齐循环中漏掉的最后一个数字n
}

136 只出现一次的数字

leetcode第136题只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

根据上面一题的按位异或的思路，这道题可以闭着眼睛写出结果：

public int singleNumber(int[] nums) {
    int num = 0;
    for (int i : nums) {
        num ^= i;
    }
    return num;
}

137 只出现一次的数字 II

这是leetcode第137题只出现一次的数字 II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]
输出: 3

这道题和上面的那一道题看起来似乎是很相似的，不同之处仅仅是在于原来是出现2次，现在是变成了3次，原来有异或的运算操作，可以让a^a=0，如果有一个操作符号使得a?a?a=0，那这个问题就迎刃而解了。好像并不存在这样的运算符，那就想想其他的方法。

首先看看异或运算符的特点，1^1=0、0^1=1、1^0=1、0^0=0，联想到加法运算，01+01=10取低位为0，所以其实就是运算符左右相加去掉进位（相当于对2取模）。如果想让三个1相加得到0，那就用十进制里面的相加然后对3取模就可以了的。

这样对这个数组里面的每个数字二进制位的每一位相加并且最后对3取模，得到的就是只出现一次的数字的每一个二进制位的结果。初步想法的代码如下：

public int singleNumber(int[] nums) {
    int bit;
    int res = 0;
    for (int i = 0; i < 32; i++) {
        bit = 0;
        for (int num : nums) {        // 计算第i位的1的个数
            bit += (num>>i)&1;
        }
        res |= (bit%3)<<i;        // 根据1的个数取模得到结果
    }
    return res;
}

这其实也是一个比较通用的解法，这里出现的次数是3次，如果换成了4次、5次也能用这个方法解决。看了很多其他人的解法，还有一个更加精妙的解法，参考这里。

在上面的解法里面，我们用一个bit来保存所有的数字的某一位的和，每个元素都是int类型的，但是这道题的最多的重复次数是3，而且我们最后需要的结果并不是这个和，而是和对3取模，所以如果能够在计算的过程中不停的取模，就能控制每一位的和小于3，最多2位的二进制数字就可以了，并不需要32位的int来保存。虽然在java里面没有一个只有2位bit的二进制数字，但是可以用两个1位的二进制数字来表示，这样整个数组用两个int类型的数字表示就可以了。上面解法的另外一个问题是整个数组被遍历了32遍，因为每计算一位都要遍历一遍，但是如果用两个int来代表的话，用适当的位操作，可以把遍历次数降低到一次！

先用lower和higher代表这个二进制数字的低位和高位，每次遇到一个二进制数字的数字的时候的变化可以用下图表示（因为遇到3取模得到0，所以不可能有lower=1 higher=1这种状态，只能是中间存在的一种过渡状态）。

num	higher(old)	lower(old)	higher(过渡)	lower(过渡)	mask(掩码)	higher(new)	lower(new)
0	0	0	0	0	1	0	0
0	0	1	0	1	1	0	1
0	1	0	1	0	1	1	0
1	0	0	0	1	1	0	1
1	0	1	1	0	1	1	0
1	1	0	1	1	0	0	0

是不是感觉有点懵逼，得到了这样的一个表格又要怎么把它变成公式呢？

首先看一下从老的状态到过渡状态，完全就是一个二进制的加法，低位的数值根据lower和num可以得到的过渡状态是lower=lower^num；而高位的数值需要得到低位的进位，也就是lower&num，然后加上原来的高位就是higher^(lower&num)，通过这两部就可以轻松计算出过渡状态的高位和低位。

过渡状态可以出现higher=1 lower=1的状态，如果是出现是4次的话，这道题就直接解决了，不用任何额外的操作就可以得到最后的新状态，但是我们这里要求的是3次，也就是当higher=1 lower=1的时候需要把两位同时置零，为其他的状态时就保持不变。这个时候就要用到掩码，先计算出掩码，再通过掩码把过渡状态修正成最终的状态。掩码时根据过渡状态的高低位决定的，如果过渡状态的高低位组成的数字达到了我们想要的阈值（这道题里面是3），掩码变成0，高低位同时进行&操作置零；没有达到的时候就是1，使用&操作相当于维持原来的值。可以看到这道题当higher=1 lower=1时掩码mask=0，其他时候mask=1，很熟悉的操作，这不就是mask=~(higher&lower)吗！这道题已经水落石出了！

最后的新状态直接用过渡状态和掩码按位与，higher=higher&mask和lower=lower&mask就到了新的值。

遍历完了整个数组之后，出现了三次的数字计算得到的higher和lower一定是0，出现了一次的数字的higher一定也是0，而lower低位就是表示的出现一次的数字的二进制位的值，所以最后得到的lower就是需要的返回结果。

public int singleNumber(int[] nums) {
    int higher = 0, lower = 0, mask = 0;
    for (int num : nums) {
        higher = higher^(lower&num);
        lower  = num^lower;
        mask = ~(higher&lower);       // 计算掩码
        higher &=mask;
        lower &= mask;
    }
    return lower;
}

上面的求解过程简单点来将就是先用加法得到过渡状态，再用掩码计算出最终的新状态，对于任何出现了k次的数组中找到只出现了一次的数字的题目都能用，这里只有两位（一个高位，一个低位）。如果k=5，那么2位就不够了，需要3位数字来表示s1、s2和s3，而掩码的计算就变成了mask = ~(s3&~s2&s1)（当过渡状态为101的时候掩码为0）。

如果把上面的掩码的计算变成了mask=~(higher&~lower)，这段代码就可以直接放到只出现一次的数字这道题里面。

除了使用过渡状态，还可以使用卡诺图来直接解决新老状态转换的问题，具体的解题方法可以看这个帖子。

260 只出现一次的数字 III

这是leetcode第260题只出现一次的数字 III

给定一个整数数组nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]
注意：

结果输出的顺序并不重要，对于上面的例子，[5, 3]也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

这道题和上面的不同之处在于上面需要求解的元素的出现次数只是一次，得到最后一个元素就可以了，然而这道题需要求解两个出现一次的元素。比如这两个元素分别是a和b，一次遍历经过按位异或之后得到的结果是a^b，从这个信息里面我们貌似什么结论都得不到。

既然要得到两个数字，需要遍历两次，如果两次都全部遍历，我们想要的信息就会混在一起，唯一的方法就是把这个数组分成两个子数组，一个数组包含a，另一个包含b，这样分别遍历就能够得到想要的a和b了。

要想拆分这个数组，需要区分a和b，由于a和b一定是不同的，二进制表示的32位里面一定有1位是不同的，找到了这一位，然后把整个数组里面这一位为1的和为0数字分别列为两个子数组（同一个数字肯定会被划分到同一个子数组里面），分别异或就能够得到结果了。为了找到a和b不同的二进制位，上面得到的a^b就能派上用场了，异或结果为1的肯定是两个数字不同的那一位，随便找一个就可以区分，这里我们直接为1的最低位。在文章的开头就有获取最低位的1的操作——num&(-num)，可以直接使用，简化的代码如下：

public int[] singleNumber(int[] nums) {
    if (nums == null || nums.length < 1) return null;
    int[] res = new int[2];
    int xor = 0;
    for (int num : nums) {   // 计算a^b
        xor = xor^num;
    }
    int bits = xor & (-xor); // 获取最低位1

    for (int num : nums) {   // 获取其中一个出现次数位1的数字a
        res[0] ^= (bits & num) == bits ? num : 0;
    }
    res[1] = res[0]^xor;     // 根据根据前面的数字得到另一个数字b
    return res;
}

338 比特位计数

这是leetcode第338题比特位计数

给定一个非负整数num。对于0 ≤ i ≤ num范围中的每个数字i，计算其二进制数中的1的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]

示例 2:

输入: 5
输出: [0,1,1,2,1,2]

进阶:

给出时间复杂度为O(nsizeof(integer))的解答非常容易。但你可以在线性时间O(n)*内用一趟扫描做到吗？
要求算法的空间复杂度为O(n)。

看完这道题，看到最后的进阶部分，是不是感觉到很眼熟——要求线性时间内解决问题，空间复杂度位O(n)——这不就是动态规划吗！想想这道题的问题的特点，找找最优子结构。

对于一个二进制数字n，如果想得到他的从左到右第n位中的1的个数，可以先得到它的从左到右第n-1位中的1的个数，然后根据第n位是否是1来决定是否要加1。要得到整个数字中的1的个数，就需要知道从左到右第31位（从1开始计数）中的1的个数，以及最低位是否是1。得到前者并不难，因为如果把整个数字向右移一位就是一个前面已经计算过的数字（动态规划从小到大开始计算），这就变成了最优子结构了，递推公式变成了res[i] = res[i>>1] + (i&1);，有了这个公式问题就解决了。

比如如果想得到10也就是二进制1010的1的个数，可以先找到左边三个二进制数字101的1的个数，加上最右侧的位0就可以了。

public int[] countBits(int num) {
    int[] res = new int[num+1];      // 不需要初始化，默认为0
    for (int i = 0; i < res.length; i++) {
        res[i] = res[i>>1] + (i&1);
    }
    return res;
}

187 重复的DNA序列

这是leetcode第187题重复的DNA序列

所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。

示例：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC", "CCCCCAAAAA"]

看到了前面的那么多的明摆着用位操作的题目，再跳到这个题目感觉是不是有点蒙蔽，似乎跟位操作一点关系都没有。但是注意读题，里面有两个关键的限定条件——10个字母长的序列和只有“ACGT”四个字符，看到这两个条件就联想到一个int数字有32位，所以一个int数字就能够正好代表这样的一个10个字符长的序列。

在实现中我们用

00代表A
01代表C
10代表G
11代表T

比如序列AAAAACCCCC就可以用00 00 00 00 00 01 01 01 01 01来表示，这只是从右到左的20位，更高位都是0省略掉了。

一串DNA正好需要20位，高位直接用掩码去掉。每一个唯一的DNA串都能用一个唯一的int数字表示，用一个数组来表示每一串出现的次数，数组最大长度是1<<20。

public List<String> findRepeatedDnaSequences(String s) {
    if (s == null || s.length() <= 10) return new ArrayList<>();
    char[] chars = s.toCharArray();              // 转化成数组提高效率
    int[] freq = new int[1<<20];                 // 出现频率数组
    int num = 0;                                 // 计算过程中的int值
    int mask = (1<<20)-1;                        // 掩码，只保留最低的20位
    for (int i = 0; i < 10; i++) {               // 初始化第一个DNA串
        num <<= 2;
        if (chars[i] == 'C') {
            num |= 1;
        } else if (chars[i] == 'G') {
            num |= 2;
        } else if (chars[i] == 'T') {
            num |= 3;
        }
    }
    freq[num]++;
    List<Integer> repeated = new ArrayList<>();
    for (int i = 10; i < chars.length; i++) {    // 遍历所有的长度为10的DNA串
        num <<= 2;                               // 清楚最高的两位，也就是移除滑出的字符串
        if (chars[i] == 'C') {
            num |= 1;
        } else if (chars[i] == 'G') {
            num |= 2;
        } else if (chars[i] == 'T') {
            num |= 3;
        }
        num &= mask;                             // 掩码 保留最低的20位
        freq[num]++;                             // 统计出现频率
        if (freq[num] == 2) repeated.add(num);   // 只有出现次数是2的时候才计入，避免重复
    }

    List<String> res = new ArrayList<>(repeated.size());
    for (Integer integer : repeated) {           // 将int数字转化成DNA串
        char[] seq = new char[10];
        for (int i = 9; i >= 0; i--) {
            switch (integer&3) {
                case 0:seq[i]='A';break;
                case 1:seq[i]='C';break;
                case 2:seq[i]='G';break;
                case 3:seq[i]='T';break;
            }
            integer >>=2;
        }
        res.add(new String(seq));
    }
    return res;
}

总结

这篇文章主要主要讲解了二进制位操作的几个基本的使用方法和小技巧，顺带提了一下浮点型数字的表示方法，希望能够增加对计算机底层的数据的理解。

后面讲到了几个leetcode上面的比较经典的题目比如两数相除和只出现一次的数字，都是使用位运算解决实际的问题，而重复的DNA序列是更高层次的通过位运算解决问题的案例。

洋洋洒洒写了几千字，希望帮助大家加深对位运算的理解，并能够熟练运用在工作学习中。

参考

A summary: how to use bit manipulation to solve problems easily and efficiently
Bit Manipulation 4% of LeetCode Problems
Bit Twiddling Hacks
Bitwise operators in Java
9.1 Floating Point
java浮点数的二进制格式分析
 How is a floating point number represented in Java?
执行时间1ms，击败100%
详细通俗的思路分析，多解法
 Detailed explanation and generalization of the bitwise operation method for single numbers
Bitwise Hacks for Competitive Programming
Bit Tricks for Competitive Programming

更多内容请看我的个人博客

leetcode实战—位运算（两数相除、只出现一次的数字、重复的

前言

简介

leetcode相关题目

371 两整数之和

29 两数相除

191. 位1的个数

268 缺失数字

136 只出现一次的数字

137 只出现一次的数字 II

260 只出现一次的数字 III

338 比特位计数

187 重复的DNA序列

总结

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法