开启掘金成长之旅！这是我参与「掘金日新计划 · 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