美文网首页数据结构和算法分析
面试精选之位操作问题集锦

面试精选之位操作问题集锦

作者: JohnnyShieh | 来源:发表于2017-12-28 11:23 被阅读92次

    Java 中位运算符有与(&)、或(|)、非(~)、异或(^)、左移(<<)、右移(>>)、无符号右移(>>>),只针对 int 类型有效,也可以作用于 byte、short、char、long,当为这四种类型时,JVM 会先把它们转换为 int 再操作。使用位运算符可以优化一些场景的运行速度,有时也可以简化代码,掌握一些位操作的技巧还是很有必要的,下面是我总结的 LeetCode 上一些位操作算法问题。

    1. 在 O(n)时间内求 0 ~ N 的所有整数的二进制表示中 1 的个数

    LeetCode 338. Counting Bits

    题目描述:给定一个非负整数 num,求 0 到 num 所有数的二进制表示中 1 的个数,最好在一次遍历 O(n)时间内完成,而且不能使用内置 API。

    分析:求二进制表示中 1 的个数可以使用 Integer.bitcount() 实现,但是题目要求不能使用其他内置函数,所以好像没什么办法可以 O(1) 时间内求一个数的 bitcount。这种情况下,可以看下实际的例子。

    0 1 2 3 4 5 6
    0 1 10 11 100 101 110
    0 1 1 2 1 2 2

    上面表格中第二行为 int 的二进制表示,第三行为 bit 为 1 的个数,仔细观察可以发现每个 num 的 bitcount 为 1 加上 除去最高位后的 bitcount,例如 2 的 bitcount 为 1 加上 0 的bitcount,3 的 bitcount 为 1 加上 1 的 bitcount,6 的 bitcount 为 1 加上 2 的 bitcount。所以可以通过 0 和 1 的 bitcount,计算出之后每个数的 bitcount。

    代码如下:

    // 在 O(n)时间内求 0 ~ N 之间整数的 bitcount
    public int[] countBits(int num) {
        if (0 == num) {
            return new int[]{0};
        }
        if (1 == num) {
            return new int[]{0, 1};
        }
        int[] bitCounts = new int[num + 1];
        bitCounts[0] = 0;
        bitCounts[1] = 1;
        int offset = 1;
        for (int i = 2; i <= num; i ++) {
            if (offset * 2 == i) {
                offset = i;
            }
            bitCounts[i] = bitCounts[i - offset] + 1;
        }
        return bitCounts;
    }
    

    除了上面的解法外,计算 bitcount 还有其他方式,b[n] = b [n >> 1] + n & 1,b[n >> 1] 为 n 除去最后一位的 bitcount,再加上 n & 1 为最后一位是否为 1。

    2. 给定包含不同整数的集合,返回它的所有可能子集

    LeetCode 78. Subsets

    题目描述:返回一个整数集合的所有子集,子集不能重复

    分析:对于任何一个子集,第 i 个整数是否包含,可以使用一个整数的第 i 位是否为 1 表示,所以从 0 ~ 2^n - 1 个整数刚好可以对应集合的 2^n 个子集。

    // 求集合的所有子集
    public List<List<Integer>> subsets(int[] nums) {
        int setSize = (int)Math.pow(2, nums.length);
        List<List<Integer>> sets = new ArrayList<>(setSize);
        for (int i = 0; i < setSize; i ++) {
            List<Integer> set = new ArrayList<>();
            for (int j = 0; j < nums.length; j ++) {
                if (((i >> j) & 1) == 1) {
                    set.add(nums[j]);
                }
            }
            sets.add(set);
        }
        return sets;
    }
    

    3. 求 m ~ n 内所有整数进行 & 运算后的结果

    LeetCode 201. Bitwise AND of Numbers Range

    题目描述:给定 m 和 n,其中 0 <= m <= n <= 2^31 - 1,求 m ~ n 内所有整数进行 & 运算后的结果

    分析:这里求的是所有整数进行 & 运算后的结果,如果有两个整数 & 运算后为 0,那么最后结果肯定为 0。当 m 和 n 的最高位不同时,那么一定存在这么一个数 10..0,它与 n 计算的结果为 0。而 m 和 n 的最高位相同时,那么最后结果肯定包含最高位,接下来求除去最高位后的整数运算的结果,重复之前的过程即可。

    // 求 m ~ n 内所有整数进行 & 运算后的结果
    public int rangeBitwiseAnd(int m, int n) {
        if (m == n) {
            return m;
        }
        int result = 0;
        while (m < n) {
            int mHightBit = Integer.highestOneBit(m);
            int nHightBit = Integer.highestOneBit(n);
            if (mHightBit != nHightBit) {
                break;
            }
            result |= mHightBit;
            m &= (mHightBit - 1);
            n &= (nHightBit - 1);
        }
        return result;
    }
    

    4. 求二进制表示中 1 的个数

    LeetCode 191. Number of Bits

    题目描述:给定一个无符号整数,求它的二进制表示中 1 的个数。

    分析:

    1.一个无符号整数二进制有 32 位,一种通用的方式是计算 32 位 bit 是否为 1,使用 n & 1 计算最后一位是否为 1,时间复杂度为 O(32)。

    // 求二进制表示中 1 的个数
    public int hammingWeight(int n) {
        int num = 0;
        while (n != 0) {
            num += n & 1;
            n = n >>> 1;
        } 
        return num;
    }
    

    2.除了利用 n & 1 计算最后一位为 1,还有另外一种方法,n &= n - 1 可以消除最后一位为 1 的位,例如 n = 1100,那么 n - 1 = 1011,与运算之后的结果为 1000,消除了倒数第 3 位的 1 bit,为负数时也是一样,这种方式的时间复杂度与 1 的位数有关。

    // 求二进制表示中 1 的个数
    public int hammingWeight(int n) {
        int num = 0;
        while (n != 0) {
            n &= n - 1;
            num ++;
        } 
        return num;
    }
    

    3.其实 Integer 类有个静态方法 bitCount() 计算 1 的个数,采用二分法的思想,先计算每两位中 1 的个数,再计算每四位、每八位、每十六位,最后把两个十六位的个数相加。其中第一步求每两位中 1 的个数的方法很巧妙,i - (i >>> 1)即位 1 的个数,例如 11 - 01 = 10,11 中 1 的个数刚好为 2(10),对于 32 位的整数来说,移位后还需要把偶数位改为 0,所以还要和 0x55555555 进行与运算。

    // 求二进制表示中 1 的个数
    public int hammingWeight(int i) {
        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;
    }
    

    5. 反转无符号整数的 bit

    LeetCode 190. Reverse Bits

    题目描述:给定一个无符号 32 位整数,反转它的二进制表示中的 bit。

    分析:最简单的方式是每次取出最后一位,按相反顺序排列,时间复杂度为 O(32)。有没有什么优化的方式的,可以学习 bitCount 的二分法,依次反转相邻的每十六位、每八位、每四位、每两位到最后相邻的每一位。

    // 反转无符号整数的 bit
    public int reverseBits(int n) {
        // binary swap
        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;
    }
    

    6. 在 O(1) 的时间内检测一个整数是否为 2 的幂

    LeetCode 231. Power of Two

    题目描述:判断一个整数是否为 2 的幂。

    分析:首先分析 2 的幂一般是 1,10,100,1000,10000 这种类型,在 32 位二进制中只有一位为 1,其他都是 0,这种情况可以使用之前 n &= n - 1 消除最后一位 1 bit 的方式,n & (n - 1) 为 0 则表示只有一位 bit 为 1,当第 32 位为 1 时,此时为负数,不是 2 的幂,可以通过 n > 0 来排除。

    // 检测一个整数是否为 2 的幂
    public boolean isPowerOfTwo(int n) {
        return (n > 0) && (n & (n - 1) == 0)
    }
    

    7. 在 O(1) 的时间内检测一个整数是否为 4 的幂

    LeetCode 342. Power of Four

    题目描述:判断一个整数是否为 4 的幂。

    分析:和上一题相似,4 的幂一般是 1,100,10000,1000000,一个数为 4 的幂,它同时也是 2 的幂,但是 1 bit 所在的位都是奇数位,这个只需要和 0x55555555 与运算不为 0 即可。

    public boolean isPowerOfFour(int n) {
        return (n > 0) && (n & (n - 1) == 0) && (n & 0x55555555 != 0)
    }
    

    8. 找出数组中只出现一次的数

    LeetCode 136. Single Number

    题目描述:给定一个整数数组,所有元素都出现两次除了一个元素,找出只出现一次的元素。要求时间复杂度为线性的,不用额外的空间。

    分析:可以利用 n ^ n = 0 的特点,把数组所有元素进行异或运算,最后的结果就是只出现一次的那个元素。

    // 其他元素都出现两次
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int n : nums) {
            result ^= n;
        }
        return result;
    }
    

    9. 找出数组中只出现一次的数扩展:其他数都出现三次

    LeetCode 137. Single Number II

    题目描述: 如果所有元素都出现三次只有一个元素只出现一次,在线性时间复杂度内找到这个单独的元素。

    分析:

    1.元素出现三次的话就不用利用 n ^ n = 0 的特点了,整数在内存中是 32 位二进制,每位只能是 0 和 1,所以可以统计每位 1 出现的个数,再对 3 取余就是单独元素在该位上的结果。这种方式比较通用,如果其他元素都出现四、五、六次都可以利用这种思想,时间复杂度为 O(32N)。

    // 其他元素都出现三次
    public int singleNumber(int[] nums) {
        int result = 0;
        int count = 0;
        for (int i = 0; i < 32; i ++) {
            count = 0;
            for (int n : nums) {
                count += (n >> i) & 1;
            }
            result |= (count % 3) << i;
        }
        return result;
    }
    

    2.还有一种解法是用 3 个整数来表示各个 1 bit 的出现次数,one 表示只出现一次的,two 表示出现了两次,出现三次时把该位清零,时间复杂度为 O(N)。

    // 其他元素都出现三次
    public int singleNumber(int[] nums) {
        int one = 0, two = 0, three = 0;
        for (int n : nums) {
            // 上个状态的 one & n 得到出现两次的结果,再 | 之前的结果,得到出现两次以上的 bits
            two |= one & n;
            // one ^ n 就是出现一次以上的 bits
            one ^= n;
            // 再计算出现三次的 bits
            three = one & two;
            one &= ~three;
            two &= ~three;
        }
        return one;
    }
    

    3.第一种解法是将 32 位分开考虑的,有没有什么方式同时进行 32 位 bit 的对 3 取模运算呢?二进制中 1 个 bit 最多只能表示 0 和 1,当一个数出现三次时,可以用两个 bit 来表示,每两个 bit 的高位存放在一个 int 中,低位存放在另一个 int 中。用 00 表示 32 位 bit 中的某位未出现过一次(即该位没出现过 1),01 表示该位出现一次,10 表示该位出现两次,当出现三次时重置为 00,出现次数的规律变化为 00 -> 01 -> 10 -> 00,最后的结果就是低位的那个 int。根据这个关系,可以得到一个真值表:

    high_bit low_bit input high_bit_output low_bit_output
    0 0 0 0 0
    0 1 0 0 1
    1 0 0 1 0
    0 0 1 0 1
    0 1 1 1 0
    1 0 1 0 0

    如何根据上面的真值表推导出高位和低位的逻辑表达式呢?这需要用到数字电路的知识,有两种方法:

    第一种方法:以真值表内输出端“1”为准,1) 从真值表内找出输出端为“1”的各行,把每行的输入变量写成乘积形式,遇到“0”的输入时加上非号;2)把各乘积项相加,即得到逻辑表达式。

    第二种方法:以真值表内输出端“0”为准,1) 从真值表内找出输出端为“0”的各行,把每行的输入变量写成求和形式,遇到“1”的输入时加上非号;2)把各求和项相乘,即得到逻辑表达式。

    现在先推导 low_bit_output 的逻辑表达式,以 high_bitlow_bitinput 作为输入,输出端为“1”的只有两行,使用第一种方法:

    low_bit_output = ~hight_bit & low_bit & ~input +  ~hight_bit & ~low_bit & input
                   = ~hight_bit & (low_bit & ~input + ~low_bit & input)
                   = ~hight_bit & (low_bit ^ input)
    

    再推导 high_bit_output 的逻辑表达式,这里需要注意的是,如果也以 high_bitlow_bitinput 作为输入的话,在计算 low_bit_output 前需要用临时变量保存 low_bit,不然计算完 low_bit_output 后 �low_bit 已经改变了。另一种不用临时变量的方式就是以 high_bitlow_bit_outputinput 作为输入:

    high_bit_output = high_bit & ~input & ~low_bit_output + ~high_bit & input & ~low_bit_output
                    = ~low_bit_output & (high_bit & ~input + ~high_bit & input)
                    = ~low_bit_output & (high_bit ^ input)
    

    根据上面两个逻辑表达式,就很容易得出下面这种解法,时间复杂度�只有 O(N):

    // 其他元素都出现三次
    public int singleNumber(int[] nums) {
        int low = 0, high = 0;
        for (int n : nums) {
            low = ~high & (low ^ n);
            high = ~low & (high ^ n);
        }
        return low;
    }
    

    这种利用真值表推导的方法具有非常好的扩展性,如果求一个只�出现两次的数,只需要返回 high 即可,而且对于�其他所有数都出现五次或者七次也可以用这种方式解决,只需要增加输入位数即可。

    10. 找出数组中只出现一次的数扩展:有两个数只出现一次

    LeetCode 260. Single Number III

    题目描述:数组中所有的数都出现两次,只有两个数只出现一次,要求在线性时间复杂度内完成。

    分析:假设两个只出现一次数为 x 和 y,继续利用 n ^ n = 0 的特点,所有元素异或的结果为 x ^ y。如何找出 x 和 y 呢,�可以根据 x 和 y 某一位 bit 不同把数组分为两个子数组,x 和 y 分别在两个子数组,其他成对出现的元素要么两个都在 x 所在的数组,要么两个都在 y �所在的�数组,这样就转化为一开始的问题了。

    // 其他元素都出现两次,只有两个�元素出现一次
    public int[] singleNumber(int[] nums) {
        // first, get diff = x ^ y
        int diff = 0;
        for (int num : nums) {
            diff ^= num;
        }
        // second, get the last 1 bit, mean the last bit a diff b
        diff &= -diff;
        int[] result = {0, 0};
        // divide array to two group
        for (int num : nums) {
            if ((num & diff) == 0) {
                result[0] ^= num;
            } else {
                result[1] ^= num;
            }
        }
        return result;
    }
    

    11. 求数组中两个整数最大的异或结果

    LeetCode 421. Maximum XOR of Two Numbers in an Array

    题目描述:给定一个非空数组,里面的元素都是非负整数,在 O(N) 时间内求数组中两个元素最大的异或结果。

    分析:�正常思路很难在 O(N) 时间内完成,这时可以考虑���分成 32 位 bit 来考虑,题目是求最大的异或结果,可以从结果的高位算起,从低到高的第 32 位肯定为 0,表示为�非负数。那么怎么知道第 31 位是否为 1 呢?假设�最大的异或结果的第 31 位是否为 1,那么数组中肯定有两个数的异或结果的第 31 位是否为 1,根据 t = a ^ b, b = a ^ t 的特点,如果�数组存在一个数 a,�而且 a ^ t 也在数组,说明存在两个数异或后在第 31 位为 1,那么最大的异或结果的在第 31 位为 1。然后�判断第 30 位,这时要加上第 31 位的结果,循环直到第 1 位。时间复杂度为 O(31N),也相当于 O(N)。

    // 求数组两个数最大异或结果
    public int findMaximumXOR(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        int max = 0, mask = 0;
        for (int i = 30; i >= 0; i --) {
            mask |= 1 << i;
            Set<Integer> set = new HashSet<>();
            // 提取数组的前缀
            for (int n : nums) {
                set.add(n & mask);
            }
            int t = max | (1 << i);
            // 如果 t = a ^ b, b = t ^ a 一定在 sets 中
            for (int prefix : set) {
                if (set.contains(t ^ prefix)) {
                    max = t;
                    break;
                }
            }
        }
        return max;
    }
    

    12. 总结

    仔细思考上面 11 道位操作的算法题后,我总结出下面一些特点,牢记这些特点以后遇到位操作的算法题后就每那么难了:

    1. 整数在计算机中是以 32 位二进制表示的,可以把 32 位拆分开思考问题,上面很多的题目都利用了这种思想。

    2. 对于单个整数的操作,例如 bitCount、reverseBit,可以采用二分法,简化问题。

    3. n & (n - 1) 可以消除 n 中最后一位 1 bit,n & (- n)可以得到最后一位 1 bit。

    4. n ^ n = 0,这个特点可以消除重复出现的数。

    5. 可以利用数字电路的知识,用真值表推导逻辑表达式,Single Number II 的最后一种解法非常值得借鉴。

    6. 异或运算符有个特点 t = a ^ b, b = a ^ t

    参考文章:

    相关文章

      网友评论

        本文标题:面试精选之位操作问题集锦

        本文链接:https://www.haomeiwen.com/subject/novmgxtx.html