开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第9天，点击查看活动详情^[1]

位运算

1.十进制与二进制的转换

位运算是针对于2进制而言，所以进行运算时首先要将数字进行转换2进制，这里介绍8421法

十进制 二进制

1 0001

2 0010

4 0100

8 1000

16 10000

.....

这就是所谓8421法，这样可以很快进行十进制和二进制的转换

如5=4+1

0100+0001=0101

2.模板

(1)求n的第k位数字: n >> k & 1

那么我们这里就要先理解一下>>和<<运算符了

1)<<左移运算符 5<<2 左移两位 0101<<2-->0101 00=20 将一个运算对象的各二进制位全部左移若干位（左边的二进制丢弃，右边补0） 对于一个正数(无符号数)而言，左移1位就相当于*2，可以参考上面的8421法就可得知

2）>>右移运算符 5>>2 右移两位 0101>>2-->0001|(01)=1 正负数右移就不一样了 将一个运算对象的各二进制位全部右移若干位，正数左补0，负数左补1. 对于一个正数(无符号数)而言，左移1位就相当于/2，可以参考上面的8421法就可得知

3）& 按位与 这里要与&&进行区分，&&是逻辑运算符 所得到的结果真/假，只适用于编程语言中 因为不同语言的返回值不同，比如Java返回是true/false，C返回1/0 1&&0=假 1&&1=真，0&&0=假， 而&是按位运算符 使用范围较广，算法 即全1为1，其他全为0 1&1=1，1&0=0，0&0=0

解释模板： 理解了上面三种运算符，就可以很好解释该模板 n>>k:求第几位就左移几位，注意这里的第几位是从右向左算，并且0开始。使得所求位成为最后一位 &1:1转换为二进制即 00000000000000001，前面全0，只有最后一位为1，所以只会求得最后一位

(2).返回n的最后一位1：lowbit(n) = n & -n

&是二进制的运算

所以这里需要理解一个概念

-n的原码=n的原码取反+1（~n+1), ~就是取反的意思

5(0101)

~5(1010)

~5+1(1011)

所以5&(-5)=(0101)&(1011)=(0001) 得到的最后一位1为0001 ，第二个1是 0100=4

为什么这样可以得到最后一位1呢，我由图解释

我们可以得到最后一位1之后的所有位都为0，取反 后最后一位1变成了0，后面所有的0都变成了1，此时再+1 ,后面的1都会形成进位到最后一位1所取反的0

(鼠标画图太难了，以后用平板画🥲)

(3)实际应用

801. 二进制中1的个数 - AcWing题库

给定一个长度为 nn 的数列，请你求出数列中每个数的二进制表示中 1的个数。

通过上面模板我们可以求出最后一位1的数，我们可以去掉最后一位1的数，然后使得倒数第二位1的成为最后一位

#include<iostream>
using namespace std;
const int MAX=1e5+10;
int A[MAX];
int lowbit(int x)
{
    return x&(-x);  -x=~x+1 为x的补码
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int res=0;
        cin>>A[i];
        //判断是否还有1
        while(lowbit(A[i]!=0))
        {
           //减去最后一位1的数，下一次判断就是倒数第二位的了
         A[i]-=lowbit(A[i]);res++;
        }
        cout<<res<<" ";
    }
    return 0;
}

位运算是针对于二进制而言，所以多于很多还不了解二进制运算的帅读者有点困难，但理解原理便变得通达了，毕竟二进制除了位数较多外，它的值只有1/0

感谢观看。😁

参考资料

[1]

https://juejin.cn/post/7167294154827890702: https://juejin.cn/post/7167294154827890702