作者主页作者简要描述算法篇Linux篇QT百日筑基篇数据结构篇基础位运算目录/索引目录基础位运算目录/索引位运算宝典位运算宝典1: 基础位运算位运算宝典2: 给定一个数n 确定他的二进制位的第x位是1还是0.位运算宝典3:给定一个数将他的第x位修改为1.位运算宝典4:给定一个数将他的第x位修改为0.位运算宝典5:位图的思想。位运算宝典6提取一个数n二进制表示最右侧的1位运算宝典7干掉一个数n二进制表示最右侧的1位运算宝典8位运算的优先级位运算宝典9异或运算的运算律。题目一 191. 位1的个数题目解析算法原理编写代码运行/提交题目二338. 比特位计数题目解析算法原理编写代码运行/提交题目三461. 汉明距离题目解析算法原理编写代码运行/提交扩展__builtin_popcount题目四136. 只出现一次的数字题目解析算法原理编写代码运行/提交在学习位运算时我们要首先的了解一些位运算的基础知识.位运算宝典位运算宝典1: 基础位运算 左移特点: 尖部分指向左侧所以是左移一般数左移会将自身缩小2倍。例如 2 1 0010 - 0001 从2到一。 2位就是2的次方倍 42 1。 : 右移特点: 尖部分指向左侧所以是右移一般数左移会将自身扩大2倍。例如 2 1 0010 - 0100 从2到4。~ 取反特点: 将自身的二进制进行相反的处理 原来是1变0是0变1.例如: 0101 ——取反 1010. 按位与特点: 有0为0两个都是1才为1.例如:0011 0101 0001.| 按位或特点: 有1为1两个都是0才为0.例如:0011 | 0101 0111.^ 按位异或特点相同为0 相异为1。 / 无进位相加。例如:0011 ^ 0101 0110.位运算宝典2: 给定一个数n 确定他的二进制位的第x位是1还是0.答案 (nx) 1 是0则为0 是1则为1.位运算宝典3:给定一个数将他的第x位修改为1.答案 n | (1x)位运算宝典4:给定一个数将他的第x位修改为0.答案n ~(1 x)位运算宝典5:位图的思想。答案哈希思想。 给定一个int能表示32位的比特位。如果一个数组的第二位是否有数我们只要查看这个int的第二位是否为1即可。位运算宝典6提取一个数n二进制表示最右侧的1答案 n -n位运算宝典7干掉一个数n二进制表示最右侧的1答案: n ((~n)1) / n(n-1)位运算宝典8位运算的优先级答案 管什么优先级能加括号就加括号。~ ^| 尽量加括号位运算宝典9异或运算的运算律。答案 异或遵循异或交换律。题目一 191. 位1的个数题目解析题目所人话就是给一个数让我们看看他的二进制有几个1.算法原理方法一我们可以循环的进行移动。添加一个计数的变量。我们将n和1进行如果这个结果为1就将这个计数的变量进行。然后继续的进行左移。 循环结束的标志就是我们的n为0.为0了就代表后面没有1了。方法二速度更快采用宝典7。 我们用宝典7每一次都干掉最右侧的1. 知道将所有的1都干掉。结果也就为0了。编写代码方法一class Solution { public: int hammingWeight(int n) { int ret; while(n) { if(n 1) ret; n n 1; } return ret; } };方法二class Solution { public: int hammingWeight(int n) { int cnt 0; while (n) { cnt; n n - 1; } return cnt; } };运行/提交题目二338. 比特位计数题目解析我们从0到n这中间的数所包含1的个数。 将他们放到ans数组中。例如 : 1 : 0001 包含1个1所以我们的返回数组ans[1]1;3: 0101 包含两个1 所以我们的返回数组ans[3]2算法原理这里我们要进行将所有的数组放到ans中所以要进行遍历一边这个数组。一定要进行一个for。我们要在内部是判断这个i位置有几个1这就回到我们题目一的方法了。当然我们这里要创建一个数组来进行返回。我这里习惯将vector命名为dp编写代码class Solution { public: vectorint countBits(int n) { vectorint dp(n 1); dp[0]0; for(int i1;in;i) { int ret0,ni; while(n) { n (n - 1); ret1; } dp[i]ret; } return dp; } };运行/提交题目三461. 汉明距离题目解析我们计算一个数二进制的两个数的不同位置。算法原理我们可以先让x和y疑惑一下。这样可以让我们的不同位置直接的变成1.然后我们直接找异惑玩的位置是1就好了 即此题就是在找异惑1的个数。我们让x异或完的数的值给s 我们找s中的1的个数就好了ss-1是最简单的找1的因为后最前面的1会直接的进行消除。我们这时候创建一个变量就行了。计数然后最后的时候进行返回就好了。编写代码class Solution { public: int hammingDistance(int x, int y) { //取出最右侧的1的位置 int s x ^y; int ret0; while(s) { ss-1; ret; } return ret; } };运行/提交扩展__builtin_popcount这里提供一个函数__builtin_popcount是GCC/Clang 编译器内置函数不属于标准库不用包含任何头文件就能直接使用。 只要是.c/.cpp文件正常编译即可调用。builtin:执行内建的函数, popcount:爆米花作用 计算一个数字中二进制形式1的个数。ai关键词__builtin_popcount介绍一下这个函数并给出如何去使用。函数的说明豆包ai生成__builtin_popcount 完整介绍与使用教程一、基础介绍1. 作用GCC/Clang 编译器内置函数计算一个无符号整数二进制中 1 的个数汉明重量底层调用 CPUpopcnt硬件指令速度远快于手写循环统计。2. 三个版本严格区分类型混用会出错函数名参数类型适用整数范围__builtin_popcountunsigned int32 位普通 int 数字__builtin_popcountlunsigned long64 位 longlong 类型__builtin_popcountllunsigned long long64 位长长整型大数、状压 DP 常用3. 关键特性无需头文件编译器内置不用#include任何库仅 GCC/Clang 可用Windows MSVC (VS) 不支持禁止直接传负数有符号负数会按补码处理统计出大量 1必须强转无符号。class Solution { public: int hammingDistance(int x, int y) { return __builtin_popcount(x^y); } };题目四136. 只出现一次的数字题目解析给定我们一个数组 我们要在这个数组中找到哪个只出现一次数字的那个数字。算法原理我们注意到^x^x0, 0^xx;这两个性质并且异或支持交换率所以我们可以创建一个ret让他等于0然后每一次进入数组都进行一次异或。图解编写代码class Solution { public: int singleNumber(vectorint nums) { int ret0; for(auto e:nums) { ret ^e; } return ret; } };运行/提交