算法基础算法

位运算疑难杂症

字数统计: 1.2k字   |   阅读时长: 5分
, ,

摘要: 位运算的疑难问题集锦

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 位运算操作 中我们梳理了基础的位运算的运算符、各种集合操作用位运算的实现方式、以及其他比较常见的位运算的问题及其代码实现。本文我们看几个使用位运算的比较难的操作和问题。

位运算操作

成对变换

对于 $n >= 0$：

  • n 为偶数: x ^ 1 = n + 1
  • n 为奇数: n ^ 1 = n - 1

因此，0与1，2与3，4与5，…，关于 ^ 1 运算构成成对变换

这个特性常用于图论邻接表中边集的存储。在具有无向边(双向边)的图中把一对正反方向的边分别存储在邻接表中的 n 与 n + 1 位置(n 为偶数)，就可以通过对当前边 (x, y) 做 ^ 1 运算获得反向的边 (y, x)。

lowbit

lowbit(n) 是非负整数 n 在二进制表示下“最低位的1以及其后面的所有0构成的数值”。在文章 位运算操作 中我们提到 lowbit(n) = n & (-n)，下面我们推导一下。

假设 n > 0，n 的第 k 位是 1，且 0 ~ k - 1 位是 0。先把 n 取反，此时第 k 位变为 0，第 0 ~ k - 1 位变为 1，再将取反后的值自增 1，也就是 n = (~n) + 1。取反加一后，n 的第 k + 1 到最高位与原数相反，因此 n & (~n + 1) 只有第 k 位是 1，其余位都是 0。在补码表示下，~n = -1 - n，因此：

1
lowbit(n) = n & (~n + 1) = n & (-n)

lowbit 配合哈希算法，可以找出二进制下所有是 1 的位：

1
2
3
4
5
6
while(n > 0)
{
    int x = (n & -n);
    // x 表示其中一个是 1 的位
    n -= x;
}

lowbit 也是树状数组的一个基本运算，以后遇到的时候再详细展开。

位运算问题

题目1：位运算实现 max(a, b)

编写一个方法，找出两个数字a和b中最大的那一个。不得使用if-else或其他比较运算符。

示例：

1
2
输入： a = 1, b = 2
输出： 2

代码 (C++)

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int maximum(int a, int b) {
        using ll = long long;
        // max(a, b) = (a + b + abs(a - b)) / 2
        ll diff = (ll)a - (ll)b;
        diff = (diff ^ (diff >> 63)) - (diff >> 63);
        return (a + (ll)b + diff) / 2;
    }
};

题目2

给定一个正整数 n ，你可以做如下操作：

如果 n 是偶数，则用 n / 2替换 n 。
如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
返回 n 变为 1 所需的 最小替换次数 。

提示：

1
1 <= n <= 2^31 - 1

示例 1：
输入：n = 8
输出：3
解释：8 -> 4 -> 2 -> 1

示例 2：
输入：n = 7
输出：4
解释：7 -> 8 -> 4 -> 2 -> 1
或 7 -> 6 -> 3 -> 2 -> 1

示例 3：
输入：n = 4
输出：2

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int integerReplacement(int n) {
        using ll = long long;
        ll iter = n;
        int cnt = 0; // 记变为 1 的次数
        while(iter > 1)
        {
            if(iter == 3)
                iter -= 1;
            else if((iter & 3) == 3)
                iter += 1;
            else if((iter & 1) == 1)
                iter -= 1;
            else
                iter >>= 1;
            ++cnt;
        }
        return cnt;
    }
};

题目3

下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。

提示:

1
2
num的范围在[1, 2147483647]之间；
如果找不到前一个或者后一个满足条件的正数，那么输出 -1。

示例1:
输入：num = 2（或者0b10）
输出：[4, 1] 或者（[0b100, 0b1]）

示例2:
输入：num = 1
输出：[2, -1]

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<int> findClosedNumbers(int num) {
        if(num == INT_MAX)
            return {-1, -1};
        vector<int> result({-1, -1});
        int n = (~num);
        int p = n & (-n);
        int i = log2(p);
        // 后缀有 i 个 1
        n = num & (~((1 << i) - 1));
        if(n != 0)
        {
            p = n & (-n);
            int x = n - p;
            int ii = log2(p);
            // 后缀共 ii 位, 其中 i + 1 位是 1
            // 10001   ii = 5, i = 1 右移 (ii - i)
            x |= ((1 << (i + 1)) - 1) << (ii - i - 1);
            result[1] = x;
        }
        n = num;
        int q = n & (-n);
        int j = log2(q);
        int l = 1;
        while(j < 30 && ((num >> (j + 1)) & 1))
        {
            ++j;
            ++l;
        }
        if(j != 30)
        {
            int y = (((1 << (29 - j)) - 1) << (j + 2)) & num;
            y += (1 << (j + 1));
            y += (1 << (l - 1)) - 1;
            result[0] = y;
        }
        return result;
    }
};
Share