小袁的秘密基地
  • 🙌🏻Hi there!
  • 🧑🏻‍💻学习碎片
    • Golang
    • Java
    • Python
    • C++
    • Rust
    • 计算机网络
    • 操作系统与 Linux
    • 数据存储
    • 消息队列
    • 分布式系统
    • 云原生与 DevOps
    • 网络安全
    • 数据结构与算法
    • 业务场景
  • 🧑🏻‍🏫系统性学习
    • Go 底层设计
    • Go 高手技法
    • K8s 入门实战
    • 分布式系统典型实例
    • 数据密集型应用系统设计
    • 常见设计模式总结
    • 程序数据流静态分析指北
    • MySQL 实战技巧
    • ElasticSearch 101
  • 📝Leetcode
    • 二分查找
    • 动态规划
    • 哈希表
    • 双指针
    • 数学
    • 数据结构
    • DFS
    • BFS
    • 位运算
    • 模拟
    • 剑指 Offer
    • Go CodeTop 题解
  • 🫥CQUPT
    • 算法设计与分析
    • 计算机组织与结构
    • 计算机图形学
    • 大数据导论
由 GitBook 提供支持
在本页
  1. Leetcode

位运算

上一页BFS下一页模拟

最后更新于2年前

231. 2 的幂

https://leetcode.cn/problems/power-of-two/

给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false 。

如果存在一个整数 x 使得 n == 2x ,则认为 n 是 2 的幂次方。

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }
};

通过 n & -n 获得最后一位 1,在二进制中只会有一位 1,所以那个 1 转化为十进制就为 n 。

191. 位 1 的个数

https://leetcode.cn/problems/number-of-1-bits/

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数(也被称为)。

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int sum = 0;
        while(n > 0){
            n = n & (n - 1);
            sum++;
        }
        return sum;
    }
};

通过 n = n & (n - 1) 每次都能消灭一个 1,直到 n 为 0 时退出即可。

190. 颠倒二进制位

https://leetcode.cn/problems/reverse-bits/

颠倒给定的 32 位无符号整数的二进制位。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for(int i = 0; i < 32; i++){
            res = (res << 1) + (n >> i & 1);
        }
        return res;
    }
};

每次将 res 左移一位,值得一提的是 res << 1 与 res * 2 相等。然后取出 n 的第 i 位即可。

50. Pow(x, n)

https://leetcode.cn/problems/powx-n/

实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。

class Solution {
public:
    double myPow(double x, int n) {
        typedef long long ll;
        double res = 1;
        for(ll i = abs(ll(n)); i; i >>= 1) {
            if(i & 1) res *= x;
            x *= x;
        }
        if(n < 0) return 1 / res;
        return res;
    }
};

按照定义,计算 x 的 n 次方是将 nn 个 x 连乘,效率比较低,会超时。因为乘法具有结合律,考虑每次将一部分连乘批量计算好,作为最终答案的一部分。这就可以将 n 进行二进制拆分,若 n 的二进制位的第 k 位是 1,则 ans 可以乘上 x2k。 而计算 x2k,只需每次将自身做平方即可。

136. 只出现一次的数字

https://leetcode.cn/problems/single-number/

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

你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(auto i : nums) res ^= i;
        return res;
    }
};

进行异或操作。

📝
汉明重量