位运算常见操作整理（C++实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了位运算常见操作整理（C++实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2261字，纯文字阅读大概需要4分钟。

内容图文

1的个数

解法 1：

用 n & 1 判断最右边一位是否为 1，右移之后继续判断最右边一位，重复直到 n = 0。时间复杂度为 O(log2n)

#include <iostream>
using namespace std;
int main() {
    int n = 0b1101, cnt = 0;
    while (n) {
        cnt += n & 1;
        n >>= 1;
    }
    cout << cnt << endl;
    return 0;
}

解法 2：

用 n & (n - 1) 可以消去最右边的 1，重复直到 n = 0。时间复杂度为 O(count)，取决于 1 的个数 count，所以这种方法优于第一种。

#include <iostream>
using namespace std;
int main() {
    int n = 0b1101, cnt = 0;
    while (n) {
        n = n & (n - 1);
        ++cnt;
    }
    cout << cnt << endl;
    return 0;
}

判断某一位为 1 还是 0

判断从右数起第 k 位，(n >> (k - 1)) & 1

#include <iostream>
using namespace std;
int main() {
    int n = 0b1101;
    cout << (n >> 1 & 1) << endl;  // 第 2 位为 0
    cout << (n >> 2 & 1) << endl;  // 第 3 位为 1
    return 0;
}

反转某一位

反转从右数起第 k 位，n ^ (1 << (k - 1))

#include <iostream>
using namespace std;
int main() {
    int n = 0b1101;
    cout << (n ^ (1 << 2)) << endl;  // 反转第 3 位 -> 1001
    cout << (n ^ (1 << 1)) << endl;  // 反转第 2 位 -> 1111
    return 0;
}

一些实用的规律

一个数按位异或同一个数两次（n ^ x ^ x），值不变。

#include <iostream>
using namespace std;
int main() {
    int n = 13, x = 666;
    cout << (n ^ x ^ x) << endl;  // 仍然是 13
    return 0;
}

用按位与代替模，判断奇偶性，效率更高。n & 1 的结果为 0 就是偶数，结果为 1 就是奇数。

#include <iostream>
using namespace std;
int main() {
    cout << (4 & 1) << endl;
    cout << (5 & 1) << endl;
    return 0;
}

左移 k 位相当于乘 2 的 k 次幂，右移 k 位相当于除以 2 的 k 次幂。在分治策略中很常见，例如归并排序：

#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

void partition(int a[], int l, int m, int r) {
    int *t = new int[r - l + 1];
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r) t[k++] = a[i] < a[j] ? a[i++] : a[j++];
    while (i <= m) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];
    for (int i = l; i <= r; ++i) a[i] = t[i - l];
    delete[] t;
}

void merge_sort(int a[], int l, int r) {
    if (l < r) {
        int m = (l + r) >> 1;  // 相当于 (l + r) / 2
        merge_sort(a, l, m);
        merge_sort(a, m + 1, r);
        partition(a, l, m, r);
    }
}

int main() {
    srand(time(0));
    int a[20];
    for (int i = 0; i < 20; ++i) a[i] = rand() % 100;
    merge_sort(a, 0, 19);
    for (int i = 0; i < 20; ++i) cout << a[i] << " ";
    return 0;
}

• 点赞
• 收藏
• 分享
• • 文章举报

内容总结

以上是互联网集市为您收集整理的位运算常见操作整理（C++实现）全部内容，希望文章能够帮你解决位运算常见操作整理（C++实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端